QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#32201 | #27. The Battle for Wesnoth | Qingyu# | 100 ✓ | 100ms | 40392kb | C++23 | 2.4kb | 2022-05-18 00:55:41 | 2022-05-18 14:20:45 |
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;
static std::pair<double, int> pos[1'000'005];
static double a[1'000'005], b[1'000'005];
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: 3ms
memory: 3536kb
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: 0
Accepted
time: 2ms
memory: 3608kb
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: 0
Accepted
time: 2ms
memory: 3648kb
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: 0
Accepted
time: 3ms
memory: 3716kb
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: 0
Accepted
time: 2ms
memory: 3496kb
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: 0
Accepted
time: 2ms
memory: 3560kb
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: 0
Accepted
time: 3ms
memory: 3572kb
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: 0
Accepted
time: 2ms
memory: 3496kb
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: 0
Accepted
time: 1ms
memory: 3504kb
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: 0
Accepted
time: 5ms
memory: 4672kb
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: 3ms
memory: 3748kb
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: 0
Accepted
time: 2ms
memory: 3620kb
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: 0
Accepted
time: 3ms
memory: 3696kb
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: 0
Accepted
time: 2ms
memory: 3716kb
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: 0
Accepted
time: 2ms
memory: 3496kb
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: 3648kb
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: 0
Accepted
time: 1ms
memory: 3668kb
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: 0
Accepted
time: 2ms
memory: 3744kb
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: 0
Accepted
time: 2ms
memory: 3572kb
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 10 99 10 99 10 99 10 99 10 99 10 99 10 99 10 99 10 99 9 110 9 110 9 110 9 110 9 110 9 110 9 110 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 7 142 7 142 7 142 7 142 7 142 7 142 7 142 7 142 ...
result:
ok Output is correct
Test #20:
score: 0
Accepted
time: 1ms
memory: 3668kb
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: 0
Accepted
time: 3ms
memory: 3740kb
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: 2ms
memory: 6684kb
input:
100000 40 1 39935
output:
1 100000
result:
ok Output is correct
Test #23:
score: 0
Accepted
time: 7ms
memory: 6684kb
input:
100000 40 1 39936
output:
20000 5
result:
ok Output is correct
Test #24:
score: 0
Accepted
time: 11ms
memory: 6752kb
input:
100000 40 1 40000
output:
20000 5
result:
ok Output is correct
Test #25:
score: 0
Accepted
time: 3ms
memory: 6708kb
input:
100000 40 1 40001
output:
50000 2
result:
ok Output is correct
Test #26:
score: 0
Accepted
time: 11ms
memory: 6824kb
input:
100000 40 1 50000
output:
50000 2
result:
ok Output is correct
Test #27:
score: 0
Accepted
time: 11ms
memory: 6656kb
input:
100000 40 1 50001
output:
100000 1
result:
ok Output is correct
Test #28:
score: 0
Accepted
time: 6ms
memory: 6372kb
input:
90000 51 1 45879
output:
1 90000
result:
ok Output is correct
Test #29:
score: 0
Accepted
time: 10ms
memory: 6412kb
input:
90000 51 1 45880
output:
1836 49
result:
ok Output is correct
Test #30:
score: 0
Accepted
time: 5ms
memory: 6508kb
input:
90000 51 1 45900
output:
1836 49
result:
ok Output is correct
Test #31:
score: 0
Accepted
time: 3ms
memory: 6412kb
input:
90000 51 1 45901
output:
1914 47
result:
ok Output is correct
Test #32:
score: 0
Accepted
time: 11ms
memory: 6716kb
input:
98765 35 1 34536
output:
1 98765
result:
ok Output is correct
Test #33:
score: 0
Accepted
time: 7ms
memory: 6704kb
input:
98765 35 1 34537
output:
4938 20
result:
ok Output is correct
Test #34:
score: 0
Accepted
time: 0ms
memory: 6656kb
input:
98765 35 1 34566
output:
4938 20
result:
ok Output is correct
Test #35:
score: 0
Accepted
time: 11ms
memory: 6796kb
input:
98765 35 1 34567
output:
5809 17
result:
ok Output is correct
Test #36:
score: 0
Accepted
time: 5ms
memory: 6644kb
input:
98765 35 1 34854
output:
5809 17
result:
ok Output is correct
Test #37:
score: 0
Accepted
time: 7ms
memory: 6648kb
input:
98765 35 1 34855
output:
49382 2
result:
ok Output is correct
Test #38:
score: 0
Accepted
time: 5ms
memory: 6788kb
input:
98765 35 1 90000
output:
98765 1
result:
ok Output is correct
Test #39:
score: 0
Accepted
time: 2ms
memory: 6388kb
input:
88888 1 1 878
output:
1 88888
result:
ok Output is correct
Test #40:
score: 0
Accepted
time: 6ms
memory: 6268kb
input:
88888 1 1 879
output:
880 101
result:
ok Output is correct
Test #41:
score: 0
Accepted
time: 9ms
memory: 6360kb
input:
88888 1 1 880
output:
880 101
result:
ok Output is correct
Test #42:
score: 0
Accepted
time: 5ms
memory: 6748kb
input:
99999 99 1 99998
output:
99999 1
result:
ok Output is correct
Test #43:
score: 0
Accepted
time: 11ms
memory: 6704kb
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: 8ms
memory: 8392kb
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: 0
Accepted
time: 13ms
memory: 8424kb
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: 0
Accepted
time: 17ms
memory: 8364kb
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: 0
Accepted
time: 12ms
memory: 8364kb
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:
1162 86 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: 0
Accepted
time: 12ms
memory: 8500kb
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: 0
Accepted
time: 3ms
memory: 3600kb
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: 15
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #50:
score: 15
Accepted
time: 99ms
memory: 40264kb
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...
result:
ok Output is correct
Test #51:
score: 0
Accepted
time: 84ms
memory: 40392kb
input:
1000000 36 100000 4 359876 359877 363633 363634 363635 363636 363637 374999 375000 375001 375002 400000 400001 400002 499998 499999 500000 500001 736453 723574 506031 972172 859514 648143 366481 819149 752627 875395 623847 571322 795146 383492 656085 944953 722582 893690 682467 771537 855902 697156 ...
output:
1 1000000 1 1000000 90909 11 90909 11 90909 11 90909 11 90909 11 125000 8 125000 8 125000 8 200000 5 200000 5 200000 5 500000 2 500000 2 500000 2 500000 2 500000 2 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 125000 8 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000...
result:
ok Output is correct
Test #52:
score: 0
Accepted
time: 100ms
memory: 40308kb
input:
1000000 60 100000 5 599767 599768 599769 599770 599999 600000 600001 600002 600003 666666 666667 666668 666669 666670 666671 666672 666673 822636 802855 744019 696804 911073 884045 864895 782475 931178 830032 918518 916168 888345 635263 900435 978864 911162 721442 986746 965673 602090 628896 814409 ...
output:
163 6134 1 1000000 200000 5 200000 5 200000 5 200000 5 200000 5 333333 3 333333 3 333333 3 333333 3 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 ...
result:
ok Output is correct
Test #53:
score: 0
Accepted
time: 95ms
memory: 40332kb
input:
1000000 40 100000 6 399794 399795 400000 400001 400002 400003 400004 500000 500001 500002 500003 500004 706945 732340 750640 841586 415645 783855 924720 903698 506980 529402 993218 418446 883021 431946 817752 663314 970302 837590 608663 799219 456771 606520 409321 795114 403368 512261 699300 455655 ...
output:
1 1000000 1 1000000 200000 5 200000 5 500000 2 500000 2 500000 2 500000 2 500000 2 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 500000 2 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 500000 2 1000000 1 500000 2 1000000 1 1000000 1 1000000 1 1000000 1 ...
result:
ok Output is correct
Test #54:
score: 0
Accepted
time: 82ms
memory: 40372kb
input:
999999 37 100000 10 369853 369854 374994 374995 374996 374997 374998 399997 399998 399999 400000 499999 500000 500001 753019 976682 949142 399913 795694 694505 878400 410419 857315 784770 495528 622772 900058 413382 400640 825487 812077 633061 531086 558208 544589 647343 469984 506100 639569 992765 ...
output:
5 199999 1 999999 124999 8 124999 8 124999 8 124999 8 124999 8 199999 5 199999 5 199999 5 499999 2 499999 2 499999 2 999999 1 999999 1 999999 1 999999 1 999999 1 199999 5 999999 1 999999 1 999999 1 499999 2 999999 1 999999 1 499999 2 999999 1 999999 1 499999 2 499999 2 999999 1 999999 1 999999 1 999...
result:
ok Output is correct
Test #55:
score: 0
Accepted
time: 3ms
memory: 3648kb
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
Extra Test:
score: 0
Extra Test Passed