QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#772861 | #27. The Battle for Wesnoth | TheZone | 85 | 20ms | 15492kb | C++23 | 2.4kb | 2024-11-22 22:26:55 | 2024-11-22 22:26:56 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
const double eps = 1e-6;
template <int T>
struct fast_io {
char p[T], *p1, *p2, q[T], *q1, *q2;
fast_io() {
p1 = p2 = p, q1 = q, q2 = q + T;
fread(p, 1, T, stdin);
}
char gc() {
return *p1++;
}
void pc(char ch) {
*q1++ = ch;
}
~fast_io() {
fwrite(q, 1, q1 - q, stdout);
}
};
fast_io<1 << 21> io;
int read() {
int r = 0, neg = 1;
char ch;
do {
ch = io.gc();
} while (ch < 48 || ch > 57);
do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
return r;
}
void write(int x) {
if (x < 0) x = -x, io.pc('-');
if (x >= 10) write(x / 10);
io.pc(48 + x % 10);
}
void output(int x, char ch = ' ') {
write(x);
io.pc(ch);
}
int main() {
std::vector<int> useful_b;
int m, n;
double p;
m = read(), p = read(), n = read();
p /= 100;
std::vector<int> h(n), table(m + 1);
for (int i = 0; i < n; ++i)
h[i] = read();
for (int l = 1, r = 0; l <= m; l = r + 1) {
r = m / (m / l);
table[r] = true;
}
int sc = 0;
double f = 1, g = 1;
std::vector<std::pair<double, int>> pos(m + 1, std::make_pair(-1e18, 0));
static double a[1000005], b[1000005];
auto ins = [&](double val, int b, int i) {
int t = (m / b) * i;
pos[t] = std::max(pos[t], std::make_pair(val, b));
};
double z = (1 - p) / p, z0 = p / (1 - p);
for (int i = 1; i <= m; ++i) {
double lim = i * p;
if (sc < lim) {
++sc;
f = f - (1 - p) * g;
g = g * lim / sc;
}
else {
f = f + g * sc * (1 - p) / (i - sc);
g = g * (1 - p) * i / (i - sc);
}
if (table[i]) {
a[sc] = f, b[sc] = g;
ins(f, i, sc);
double *pa = a + sc, *pb = b + sc;
for (int j = sc - 1; j >= 1; --j) {
double bj = *pb * z * (j + 1) / (i - j);
*--pb = bj;
double aj = *pa + *pb;
*--pa = aj;
if (1 - *pb > eps) {
ins(*pa, i, j);
}
else if (i == m) {
ins(1, i, j);
}
}
pa = a + sc, pb = b + sc;
for (int j = sc + 1; j <= i; ++j) {
double bj = *pb * z0 * (i - j + 1) / j;
double aj = *pa - *pb;
*++pb = bj;
*++pa = aj;
if (*pa >= p)
ins(*pa, i, j);
}
}
}
for (int i = m; i > 0; --i)
pos[i] = std::max(pos[i], pos[i + 1]);
for (int i = 0; i < n; ++i) {
int x = 0, y = 0;
if (h[i] > m) {
x = y = 1;
}
else {
y = pos[h[i]].second;
x = m / y;
}
output(x); output(y, '\n');
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 9716kb
input:
1 30 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok Output is correct
Test #2:
score: 10
Accepted
time: 0ms
memory: 9648kb
input:
2 80 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok Output is correct
Test #3:
score: 10
Accepted
time: 2ms
memory: 9712kb
input:
3 40 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 3 3 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok Output is correct
Test #4:
score: 10
Accepted
time: 2ms
memory: 9968kb
input:
4 50 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 4 2 2 4 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok Output is correct
Test #5:
score: 10
Accepted
time: 0ms
memory: 9952kb
input:
5 20 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 5 2 2 5 1 5 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok Output is correct
Test #6:
score: 10
Accepted
time: 0ms
memory: 9712kb
input:
6 70 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 6 1 6 1 6 2 3 6 1 6 1 1 1 1 1 1 1 1 1 1 1
result:
ok Output is correct
Test #7:
score: 10
Accepted
time: 0ms
memory: 9768kb
input:
7 40 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 7 1 7 3 2 7 1 7 1 7 1 7 1 1 1 1 1 1 1 1 1
result:
ok Output is correct
Test #8:
score: 10
Accepted
time: 0ms
memory: 9764kb
input:
8 51 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 8 1 8 1 8 4 2 8 1 8 1 8 1 8 1 1 1 1 1 1 1
result:
ok Output is correct
Test #9:
score: 10
Accepted
time: 3ms
memory: 9800kb
input:
9 34 11 1 2 3 4 5 6 7 8 9 10 11
output:
1 9 1 9 3 3 4 2 9 1 9 1 9 1 9 1 9 1 1 1 1 1
result:
ok Output is correct
Test #10:
score: 10
Accepted
time: 0ms
memory: 10376kb
input:
10 1 100000 884878 751455 214308 292349 518777 621987 627497 913888 330915 676887 411803 309107 45478 905784 10996 847709 451664 824477 723026 472185 574143 254312 151912 964437 797786 350658 222631 852906 820189 19164 399894 42571 182177 533276 804359 273895 945080 658737 313612 236593 348856 74493...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok Output is correct
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #11:
score: 10
Accepted
time: 0ms
memory: 9760kb
input:
100 51 100 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
output:
1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 50 2 50 2 50 2 3 3...
result:
ok Output is correct
Test #12:
score: 10
Accepted
time: 0ms
memory: 9736kb
input:
90 40 90 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
output:
1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 18 5 18 5 45 2 45 2 45 2 45 2 45 2 45 2 45 2 45 2 45 2 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 90 1 ...
result:
ok Output is correct
Test #13:
score: 10
Accepted
time: 2ms
memory: 9932kb
input:
95 90 95 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
output:
1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 1 95 ...
result:
ok Output is correct
Test #14:
score: 10
Accepted
time: 0ms
memory: 9928kb
input:
85 3 85 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
output:
1 85 1 85 3 28 4 21 5 17 6 14 7 12 8 10 9 9 10 8 12 7 12 7 14 6 14 6 17 5 17 5 17 5 21 4 21 4 21 4 21 4 28 3 28 3 28 3 28 3 28 3 28 3 28 3 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 85 1 8...
result:
ok Output is correct
Test #15:
score: 10
Accepted
time: 0ms
memory: 9768kb
input:
84 35 84 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
output:
1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 28 3 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 42 2 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 84 1 ...
result:
ok Output is correct
Subtask #3:
score: 20
Accepted
Dependency #2:
100%
Accepted
Test #16:
score: 20
Accepted
time: 2ms
memory: 9672kb
input:
1000 51 1000 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...
output:
2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 2 500 ...
result:
ok Output is correct
Test #17:
score: 20
Accepted
time: 2ms
memory: 10016kb
input:
999 40 999 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 1...
output:
1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 1 999 ...
result:
ok Output is correct
Test #18:
score: 20
Accepted
time: 0ms
memory: 9956kb
input:
998 36 998 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 1...
output:
1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 1 998 ...
result:
ok Output is correct
Test #19:
score: 20
Accepted
time: 3ms
memory: 9792kb
input:
997 33 997 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 1...
output:
11 90 11 90 11 90 11 90 11 90 11 90 11 90 11 90 11 90 11 90 11 90 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 9 110 8 124 8 124 8 124 8 124 8 124 8 124 8 124 8 124 8 124 8 124 8 124 8 124 8 124 7 142 7 142 7 142 7 142 7 142 7 142 7 142 7 142 7 142 7 142 ...
result:
ok Output is correct
Test #20:
score: 20
Accepted
time: 0ms
memory: 9664kb
input:
996 17 996 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 1...
output:
5 199 5 199 5 199 5 199 5 199 4 249 4 249 4 249 4 249 4 249 4 249 4 249 4 249 4 249 4 249 4 249 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 3 332 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 2 498 ...
result:
ok Output is correct
Test #21:
score: 20
Accepted
time: 2ms
memory: 9984kb
input:
995 40 995 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 1...
output:
1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 1 995 ...
result:
ok Output is correct
Subtask #4:
score: 20
Accepted
Test #22:
score: 20
Accepted
time: 12ms
memory: 15448kb
input:
100000 40 1 39935
output:
1 100000
result:
ok Output is correct
Test #23:
score: 20
Accepted
time: 10ms
memory: 13368kb
input:
100000 40 1 39936
output:
20000 5
result:
ok Output is correct
Test #24:
score: 20
Accepted
time: 13ms
memory: 15396kb
input:
100000 40 1 40000
output:
20000 5
result:
ok Output is correct
Test #25:
score: 20
Accepted
time: 11ms
memory: 11336kb
input:
100000 40 1 40001
output:
50000 2
result:
ok Output is correct
Test #26:
score: 20
Accepted
time: 11ms
memory: 11404kb
input:
100000 40 1 50000
output:
50000 2
result:
ok Output is correct
Test #27:
score: 20
Accepted
time: 15ms
memory: 13448kb
input:
100000 40 1 50001
output:
100000 1
result:
ok Output is correct
Test #28:
score: 20
Accepted
time: 8ms
memory: 15216kb
input:
90000 51 1 45879
output:
1 90000
result:
ok Output is correct
Test #29:
score: 20
Accepted
time: 7ms
memory: 11004kb
input:
90000 51 1 45880
output:
1836 49
result:
ok Output is correct
Test #30:
score: 20
Accepted
time: 5ms
memory: 13120kb
input:
90000 51 1 45900
output:
1836 49
result:
ok Output is correct
Test #31:
score: 20
Accepted
time: 8ms
memory: 13152kb
input:
90000 51 1 45901
output:
1914 47
result:
ok Output is correct
Test #32:
score: 20
Accepted
time: 18ms
memory: 13456kb
input:
98765 35 1 34536
output:
1 98765
result:
ok Output is correct
Test #33:
score: 20
Accepted
time: 15ms
memory: 13448kb
input:
98765 35 1 34537
output:
4938 20
result:
ok Output is correct
Test #34:
score: 20
Accepted
time: 14ms
memory: 15492kb
input:
98765 35 1 34566
output:
4938 20
result:
ok Output is correct
Test #35:
score: 20
Accepted
time: 13ms
memory: 11416kb
input:
98765 35 1 34567
output:
5809 17
result:
ok Output is correct
Test #36:
score: 20
Accepted
time: 15ms
memory: 15076kb
input:
98765 35 1 34854
output:
5809 17
result:
ok Output is correct
Test #37:
score: 20
Accepted
time: 10ms
memory: 11044kb
input:
98765 35 1 34855
output:
49382 2
result:
ok Output is correct
Test #38:
score: 20
Accepted
time: 14ms
memory: 10968kb
input:
98765 35 1 90000
output:
98765 1
result:
ok Output is correct
Test #39:
score: 20
Accepted
time: 4ms
memory: 11088kb
input:
88888 1 1 878
output:
1 88888
result:
ok Output is correct
Test #40:
score: 20
Accepted
time: 8ms
memory: 11120kb
input:
88888 1 1 879
output:
880 101
result:
ok Output is correct
Test #41:
score: 20
Accepted
time: 3ms
memory: 13160kb
input:
88888 1 1 880
output:
880 101
result:
ok Output is correct
Test #42:
score: 20
Accepted
time: 7ms
memory: 11320kb
input:
99999 99 1 99998
output:
99999 1
result:
ok Output is correct
Test #43:
score: 20
Accepted
time: 7ms
memory: 13496kb
input:
99999 99 1 9
output:
1 99999
result:
ok Output is correct
Subtask #5:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #44:
score: 25
Accepted
time: 18ms
memory: 12088kb
input:
100000 51 100000 5 50978 50979 50980 50999 51000 51001 51002 51003 51004 51046 51047 51048 51049 51050 51106 51107 51148 51149 51150 51151 51152 51153 51219 51220 51221 51279 51280 51281 51282 51283 51337 51338 51339 51340 51425 51426 51427 51506 51507 51508 51509 51510 51511 51512 51513 51514 51515...
output:
6 16666 1 100000 2040 49 2040 49 2040 49 2040 49 2127 47 2127 47 2127 47 2127 47 2127 47 2127 47 2127 47 2222 45 2222 45 2222 45 2325 43 2325 43 2325 43 2325 43 2439 41 2439 41 2439 41 2439 41 2564 39 2564 39 2564 39 2564 39 2702 37 2702 37 2702 37 2702 37 2702 37 2857 35 2857 35 2857 35 2857 35 303...
result:
ok Output is correct
Test #45:
score: 25
Accepted
time: 19ms
memory: 14140kb
input:
100000 36 100000 2 35960 35961 35962 36360 36361 37499 37500 37501 37502 37503 40000 40001 40002 49999 50000 50001 50002 39541 44956 73170 84602 39125 42702 51253 73072 71521 36626 95734 95791 41065 57007 65391 89300 52079 38692 72419 40481 62604 63600 49707 91446 93660 56063 37021 93610 96852 74854...
output:
39 2564 1 100000 1 100000 9090 11 9090 11 12500 8 12500 8 12500 8 20000 5 20000 5 20000 5 20000 5 50000 2 50000 2 50000 2 50000 2 100000 1 100000 1 20000 5 50000 2 100000 1 100000 1 20000 5 50000 2 100000 1 100000 1 100000 1 12500 8 100000 1 100000 1 50000 2 100000 1 100000 1 100000 1 100000 1 20000...
result:
ok Output is correct
Test #46:
score: 25
Accepted
time: 10ms
memory: 14248kb
input:
100000 75 100000 7 74908 74909 93531 95992 96697 99529 96878 82040 81676 79522 82762 96352 98632 85102 79505 78022 98532 89232 82286 94290 90922 98127 94025 95641 93309 92621 81003 76084 86376 96140 94251 83399 90834 92522 96403 82961 97186 94923 99731 84060 78496 92130 98764 99952 91202 96235 95589...
output:
1 100000 1 100000 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100...
result:
ok Output is correct
Test #47:
score: 25
Accepted
time: 17ms
memory: 14248kb
input:
100000 34 100000 9 33975 33976 33977 49997 49998 49999 50000 50001 68461 47786 76759 83342 35936 75573 76429 68835 38270 66433 42243 35678 48916 92634 44041 69159 95110 89219 37883 48287 50604 81490 52206 89964 81237 80470 86741 76772 54102 82192 97643 94991 62344 71743 83369 52728 85822 89357 45034...
output:
1111 90 1 100000 1 100000 50000 2 50000 2 50000 2 50000 2 50000 2 100000 1 100000 1 50000 2 100000 1 100000 1 50000 2 100000 1 100000 1 100000 1 50000 2 100000 1 50000 2 50000 2 50000 2 100000 1 50000 2 100000 1 100000 1 100000 1 50000 2 50000 2 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 ...
result:
ok Output is correct
Test #48:
score: 25
Accepted
time: 20ms
memory: 14164kb
input:
98888 37 100000 8 36543 36544 36545 36546 37083 37084 39554 39555 39556 49444 49445 39481 61000 67101 73249 92468 70302 80749 94202 91713 96452 78425 83455 92703 65611 98006 89904 53395 93051 52399 73654 71343 52872 90774 96288 45765 83103 37270 67016 63965 61933 77759 91922 63088 68256 95585 67294 ...
output:
2 49444 1 98888 12361 8 12361 8 12361 8 12361 8 19777 5 19777 5 49444 2 49444 2 49444 2 98888 1 19777 5 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 98888 1 49444 2 9888...
result:
ok Output is correct
Test #49:
score: 25
Accepted
time: 4ms
memory: 9952kb
input:
1000 1 1000 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 ...
output:
1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 9 111 10 100 11 90 12 83 13 76 14 71 15 66 16 62 17 58 18 55 19 52 20 50 21 47 22 45 23 43 24 41 25 40 26 38 27 37 28 35 29 34 30 33 31 32 32 31 33 30 34 29 35 28 37 27 37 27 38 26 40 25 40 25 41 24 43 23 43 23 45 22 45 22 47 21 47 21 50 20 50 ...
result:
ok Output is correct
Subtask #6:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #50:
score: 0
Time Limit Exceeded
input:
1000000 51 100000 8 509927 509928 509929 509930 509931 509932 510197 510198 510199 510200 510201 510202 510203 510622 510623 510624 510625 510626 510627 511105 511106 511107 511609 511610 511611 512188 512189 512190 512191 512820 512821 513513 513514 513515 514274 514275 514276 514277 514278 514279 ...
output:
2 500000 1 1000000 1 1000000 1 1000000 1 1000000 20408 49 20408 49 20408 49 20408 49 20408 49 20408 49 21276 47 21276 47 21276 47 21276 47 21276 47 21276 47 22222 45 22222 45 22222 45 22222 45 22222 45 23255 43 23255 43 23255 43 24390 41 24390 41 24390 41 24390 41 25641 39 25641 39 27027 37 27027 37...