QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32196#27. The Battle for WesnothQingyu#100 ✓110ms42732kbC++232.8kb2022-05-18 00:51:032022-05-18 14:20:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 14:20:05]
  • 评测
  • 测评结果:100
  • 用时:110ms
  • 内存:42732kb
  • [2022-05-18 00:51:03]
  • 提交

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;	
	}
	char gc() {
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	void pc(char ch) {
		if (q1 == q2) {
			fwrite(q, 1, T, stdout);
			q1 = q;
		}
		*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();
		if (ch == '-') neg = -1;
	} while (ch < 48 || ch > 57);
	do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return r * neg;
}

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));
	};
	auto debug = [&]() {
		for (int i = 1; i <= m; ++i)
			printf("a[%d] = %.6f, b[%d] = %.6f\n", i, a[i], i, b[i]);
	};
	double z = (1 - p) / p, z0 = p / (1 - p);
	for (int i = 1; i <= m; ++i) {
		double lim = i * p;
		if (sc < lim) {
			++sc;
			double _f = f - (1 - p) * g;
			double _g = g * lim / sc;
			f = _f, g = _g;
		}
		else {
			double _f = f + g * sc * (1 - p) / (i - sc);
			double _g = g * (1 - p) * i / (i - sc);
			f = _f, g = _g;
		}
		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: 4ms
memory: 9692kb

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: 1ms
memory: 9760kb

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: 4ms
memory: 9632kb

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: 4ms
memory: 9688kb

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: 9692kb

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: 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: 0
Accepted
time: 4ms
memory: 9716kb

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: 9632kb

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: 2ms
memory: 9644kb

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: 7ms
memory: 10120kb

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: 2ms
memory: 9696kb

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: 9776kb

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: 9696kb

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: 3ms
memory: 9664kb

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: 4ms
memory: 9764kb

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: 4ms
memory: 9856kb

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: 4ms
memory: 9856kb

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: 0ms
memory: 9784kb

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: 4ms
memory: 9768kb

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: 4ms
memory: 9888kb

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: 1ms
memory: 9756kb

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: 11944kb

input:

100000 40
1
39935

output:

1 100000

result:

ok Output is correct

Test #23:

score: 0
Accepted
time: 4ms
memory: 13368kb

input:

100000 40
1
39936

output:

20000 5

result:

ok Output is correct

Test #24:

score: 0
Accepted
time: 12ms
memory: 13780kb

input:

100000 40
1
40000

output:

20000 5

result:

ok Output is correct

Test #25:

score: 0
Accepted
time: 5ms
memory: 11080kb

input:

100000 40
1
40001

output:

50000 2

result:

ok Output is correct

Test #26:

score: 0
Accepted
time: 6ms
memory: 12996kb

input:

100000 40
1
50000

output:

50000 2

result:

ok Output is correct

Test #27:

score: 0
Accepted
time: 4ms
memory: 13000kb

input:

100000 40
1
50001

output:

100000 1

result:

ok Output is correct

Test #28:

score: 0
Accepted
time: 3ms
memory: 13000kb

input:

90000 51
1
45879

output:

1 90000

result:

ok Output is correct

Test #29:

score: 0
Accepted
time: 4ms
memory: 11224kb

input:

90000 51
1
45880

output:

1836 49

result:

ok Output is correct

Test #30:

score: 0
Accepted
time: 7ms
memory: 11132kb

input:

90000 51
1
45900

output:

1836 49

result:

ok Output is correct

Test #31:

score: 0
Accepted
time: 3ms
memory: 11048kb

input:

90000 51
1
45901

output:

1914 47

result:

ok Output is correct

Test #32:

score: 0
Accepted
time: 5ms
memory: 11132kb

input:

98765 35
1
34536

output:

1 98765

result:

ok Output is correct

Test #33:

score: 0
Accepted
time: 4ms
memory: 13204kb

input:

98765 35
1
34537

output:

4938 20

result:

ok Output is correct

Test #34:

score: 0
Accepted
time: 6ms
memory: 13432kb

input:

98765 35
1
34566

output:

4938 20

result:

ok Output is correct

Test #35:

score: 0
Accepted
time: 6ms
memory: 11128kb

input:

98765 35
1
34567

output:

5809 17

result:

ok Output is correct

Test #36:

score: 0
Accepted
time: 3ms
memory: 13696kb

input:

98765 35
1
34854

output:

5809 17

result:

ok Output is correct

Test #37:

score: 0
Accepted
time: 5ms
memory: 13256kb

input:

98765 35
1
34855

output:

49382 2

result:

ok Output is correct

Test #38:

score: 0
Accepted
time: 6ms
memory: 13772kb

input:

98765 35
1
90000

output:

98765 1

result:

ok Output is correct

Test #39:

score: 0
Accepted
time: 7ms
memory: 13128kb

input:

88888 1
1
878

output:

1 88888

result:

ok Output is correct

Test #40:

score: 0
Accepted
time: 10ms
memory: 11124kb

input:

88888 1
1
879

output:

880 101

result:

ok Output is correct

Test #41:

score: 0
Accepted
time: 3ms
memory: 13252kb

input:

88888 1
1
880

output:

880 101

result:

ok Output is correct

Test #42:

score: 0
Accepted
time: 8ms
memory: 11472kb

input:

99999 99
1
99998

output:

99999 1

result:

ok Output is correct

Test #43:

score: 0
Accepted
time: 6ms
memory: 11128kb

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: 14ms
memory: 12184kb

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: 11ms
memory: 12132kb

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: 13ms
memory: 12264kb

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: 9ms
memory: 14312kb

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: 12092kb

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: 4ms
memory: 9736kb

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: 103ms
memory: 42208kb

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: 110ms
memory: 42732kb

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: 95ms
memory: 42700kb

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: 91ms
memory: 42284kb

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: 84ms
memory: 42424kb

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: 2ms
memory: 9792kb

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