Submission #00333

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
if(x > y) x = y;
}
const double EPS = 1e-10;
const double PI = acos(-1.0);
const LL MOD = 1e9+7;
LL P9;
LL fact[100010];
LL powm(LL x, LL y){
if(y == 0) return 1;
return powm(x*x%MOD, y/2) * (y%2==0?1:x) % MOD;
}
LL inv(LL x){
return powm(x, MOD-2);
}
// xをy個並べる
LL f(LL x, LL y){
return (powm(10, y) - 1 + MOD) % MOD * P9 % MOD * x % MOD;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
P9 = inv(9);
fact[0] = 1;
REP(i,100001)
fact[i+1] = fact[i] * (i+1) % MOD;
int N;
cin >> N;
vector<PLL> xs(N);
REP(i,N) cin >> xs[i];
SORT(xs);
if(N == 1){
cout << f(xs[0].FF, xs[0].SS) << endl
<< 1 << endl;
return 0;
}
LL ans_n = 0, ans_sum = 1;
if(xs[0].FF == 0){
int nzero_b = -1, nzero_e=-1;
REP(i,N)
if(xs[i].FF != 0){
if(nzero_b < 0){
nzero_b = i;
}
else{
if(xs[i].SS != xs[i-1].SS){
nzero_e = i;
break;
}
}
}
if(nzero_e == -1) nzero_e = N;
ans_n = f(xs[nzero_b].FF, xs[nzero_b].SS);
for(int i=0;i<N;++i){
if(i != nzero_b)
ans_n = (ans_n * powm(10, xs[i].SS) % MOD + f(xs[i].FF, xs[i].SS)) % MOD;
}
LL sum = 0;
ans_sum = (nzero_e - nzero_b);
REP(i,N){
if(i > 0 && xs[i].FF != xs[i-1].FF){
if(xs[i-1].FF == xs[nzero_b].FF)
--sum;
ans_sum = ans_sum * fact[sum] % MOD;
sum = 0;
}
++sum;
}
ans_sum = ans_sum * fact[sum] % MOD;
}
else{
LL sum = 0;
for(int i=0;i<N;++i){
ans_n = (ans_n * powm(10, xs[i].SS) % MOD + f(xs[i].FF, xs[i].SS)) % MOD;
if(i > 0 && xs[i].FF != xs[i-1].FF){
ans_sum = ans_sum * fact[sum] % MOD;
sum = 0;
}
++sum;
}
ans_sum = ans_sum * fact[sum] % MOD;
}
cout << ans_n << endl
<< ans_sum << endl;
return 0;
}

ステータス

項目 データ
問題 0003 - repdigit
ユーザー名 takoduki
投稿日時 2017-07-07 22:49:32
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 2813 Byte
最大実行時間 79 ms
最大メモリ使用量 3076 KB

セット

セット 得点 Cases
1 ALL 0 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 12 ms 1248 KB
1
01_sample2.in AC 13 ms 1448 KB
1
01_sample3.in AC 19 ms 1272 KB
1
02_handmake1.in AC 11 ms 1224 KB
1
02_handmake2.in WA 11 ms 1424 KB
1
02_handmake3.in WA 15 ms 1244 KB
1
02_handmake4.in AC 13 ms 1316 KB
1
02_handmake5.in AC 14 ms 1392 KB
1
02_handmake6.in AC 13 ms 1464 KB
1
02_handmake7.in AC 11 ms 1412 KB
1
02_handmake8.in AC 17 ms 1360 KB
1
02_handmake9.in AC 11 ms 1308 KB
1
03_random1.in WA 15 ms 1252 KB
1
03_random2.in WA 16 ms 1324 KB
1
03_random3.in WA 14 ms 1396 KB
1
03_random4.in AC 14 ms 1208 KB
1
03_random5.in AC 14 ms 1284 KB
1
03_random6.in AC 10 ms 1352 KB
1
04_random1.in AC 11 ms 1296 KB
1
04_random2.in AC 14 ms 1364 KB
1
04_random3.in AC 11 ms 1436 KB
1
04_random4.in AC 16 ms 1376 KB
1
04_random5.in AC 13 ms 1448 KB
1
04_random6.in AC 12 ms 1388 KB
1
05_random1.in AC 75 ms 2864 KB
1
05_random2.in AC 72 ms 3032 KB
1
05_random3.in AC 79 ms 3076 KB
1
05_random4.in AC 71 ms 2988 KB
1
06_random1.in AC 67 ms 3028 KB
1
06_random3.in AC 76 ms 2940 KB
1