QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56068#437. Fun Touriosdjfasf100 ✓190ms24868kbC++202.7kb2022-10-16 19:49:512022-10-16 19:49:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-16 19:49:54]
  • 评测
  • 测评结果：100
  • 用时：190ms
  • 内存：24868kb
查看
  • [2022-10-16 19:49:51]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
std::vector<int> createFunTour(int N, int Q);

const int N = 100010;

int root;
int siz[N], dep[N];
int b[3], tot;
vector<pair<int, int> > q[7];
vector<int> ans;

void merge()
{
	while (q[2].size())
	{
		q[1].push_back(q[2][q[2].size() - 1]);
		q[2].pop_back();
	}
	sort(q[1].begin(), q[1].end());
}

void br2()
{
	while (q[0].size() + q[1].size())
	{
		pair<int, int>now = q[0][q[0].size() - 1];
		q[0].pop_back();
		ans.push_back(now.second);
		q[0].swap(q[1]);
	}
	ans.push_back(root);
}

int C(int a, int b, int c)
{
	return a + b + c - max(a, max(b, c));
}

int nn;
void br3()
{
	if (q[0].size() == nn / 2)
	{
		merge();
		if (q[0].size() < q[1].size()) q[0].swap(q[1]);
		br2();
		return;
	}

	int flag = 0;
	while (1)
	{
		int to = flag;
		for (int i = flag + 1; i <= 2; ++i)
		{
			if (q[i][q[i].size() - 1] >= q[to][q[to].size() - 1])
				to = i;
		}

		flag = 1;
		pair<int, int>maxs = q[to][q[to].size() - 1];
		ans.push_back(q[to][q[to].size() - 1].second);
		q[0].swap(q[to]);
		q[0].pop_back();
		if (max(max(q[0].size(), q[1].size()), q[2].size()) == C(q[0].size(), q[1].size(), q[2].size()))
		{
			int now = 0;
			if (q[0].size() < q[1].size()) q[0].swap(q[1]), now = 1;
			if (q[0].size() < q[2].size()) q[0].swap(q[2]), now = (now == 0 ? 2 : now);

			if (now != 0)
			{
				if (maxs < q[((now - 1) ^ 1) + 1][q[((now - 1) ^ 1) + 1].size() - 1])
					ans.push_back(q[((now - 1) ^ 1) + 1][q[((now - 1) ^ 1) + 1].size() - 1].second), q[((now - 1) ^ 1) + 1].pop_back();
			}

			merge();
			if (now == 0) q[0].swap(q[1]);
			br2();
			return;
		}
	}
	ans.push_back(root);
}

std::vector<int> createFunTour(int n, int Q)
{
	nn = n;
	for (int i = 0; i < n; ++i) siz[i] = attractionsBehind(0, i); 
	for (int i = 0; i < n; ++i)
	{
		if (siz[i] > (n >> 1) && siz[i] < siz[root]) root = i;
	}
	for (int i = 0; i < n; ++i)
	{
		if ((dep[i] = hoursRequired(root, i)) == 1)
		{
			b[tot] = i;
			++tot;
		}
	}

	--tot;
	for (int i = 0; i < n; ++i)
	{
		if (i != root)
		{
			int to = 0;
			for (int j = 1; j <= tot; ++j)
			{
				if (hoursRequired(b[j], i) <= dep[i]) to = j;
			}
			q[to].push_back(make_pair(dep[i], i));
		}
	}

	for (int i = 0; i <= tot; ++i)
	{
		sort(q[i].begin(), q[i].end());
	}
	if (tot == 1)
	{
		if (q[0].size() < q[1].size()) q[0].swap(q[1]);
		br2();
	}
	else
	{
		if (q[0].size() < q[1].size()) q[0].swap(q[1]);
		if (q[0].size() < q[2].size()) q[0].swap(q[2]);
		br3();
	}
	return ans;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Accepted

Test #1:

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

input:

2 400000
1 0

output:

1 0

result:

ok correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 3836kb

input:

3 400000
1 0
2 0

output:

1 2 0

result:

ok correct

Subtask #2:

score: 0
Accepted

Test #3:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

4 400000
1 0
2 0
3 1

output:

3 2 1 0

result:

ok correct

Test #4:

score: 0
Accepted
time: 2ms
memory: 3680kb

input:

9 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3

output:

6 8 5 7 2 4 0 3 1

result:

ok correct

Test #5:

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

input:

14 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6

output:

10 13 9 12 8 11 7 6 4 5 3 2 1 0

result:

ok correct

Test #6:

score: 0
Accepted
time: 2ms
memory: 3692kb

input:

15 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6

output:

10 14 9 13 8 12 7 11 4 6 3 5 1 2 0

result:

ok correct

Test #7:

score: 0
Accepted
time: 2ms
memory: 3808kb

input:

16 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7

output:

15 14 10 13 9 12 8 11 7 6 4 5 3 2 1 0

result:

ok correct

Test #8:

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

input:

17 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7

output:

14 16 13 15 12 10 11 9 6 8 5 7 2 4 0 3 1

result:

ok correct

Subtask #3:

score: 0
Accepted

Test #9:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

4 400000
1 0
2 1
3 2

output:

3 0 2 1

result:

ok correct

Test #10:

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

input:

12 400000
5 4
6 5
7 6
10 9
8 10
11 8
7 11
3 7
2 3
1 2
0 1

output:

9 0 10 4 1 8 5 2 11 3 6 7

result:

ok correct

Test #11:

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

input:

17 400000
1 2
3 1
4 3
5 4
6 5
8 9
10 8
11 12
10 11
7 10
6 7
13 6
14 13
15 14
0 15
16 0

output:

16 2 12 1 9 0 11 15 8 3 14 10 4 13 5 7 6

result:

ok correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

17 400000
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15

output:

0 16 1 15 2 14 3 13 4 12 5 11 6 10 7 9 8

result:

ok correct

Subtask #4:

score: 0
Accepted

Test #13:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

4 400000
0 1
0 2
0 3

output:

3 2 1 0

result:

ok correct

Test #14:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

17 400000
6 4
3 6
8 3
7 8
13 7
15 13
2 15
11 2
14 11
9 14
5 9
1 5
12 1
10 12
16 10
0 16

output:

4 0 6 16 3 10 8 12 7 1 13 5 15 9 2 14 11

result:

ok correct

Test #15:

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

input:

17 400000
11 3
9 3
10 11
13 11
16 9
5 9
4 10
1 10
14 13
2 13
8 16
0 16
6 5
12 5
7 4
15 4

output:

12 15 8 7 6 14 0 4 16 2 5 1 9 13 3 10 11

result:

ok correct

Test #16:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

14 400000
1 11
3 1
2 3
8 2
9 8
13 8
12 13
0 12
5 13
10 5
4 10
7 11
6 7

output:

6 4 7 10 11 0 1 12 3 5 9 13 2 8

result:

ok correct

Test #17:

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

input:

15 400000
9 12
13 9
1 13
11 1
0 11
2 0
6 0
4 6
10 4
14 6
7 14
8 10
5 10
3 5

output:

12 3 9 8 13 5 1 10 11 7 2 14 0 4 6

result:

ok correct

Test #18:

score: 0
Accepted
time: 2ms
memory: 3844kb

input:

16 400000
2 6
8 2
12 6
0 12
13 0
1 13
10 1
5 10
14 0
9 10
15 9
11 15
3 11
4 3
7 3

output:

7 8 4 2 3 6 11 14 15 12 9 0 5 13 10 1

result:

ok correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

17 400000
8 11
6 8
3 6
9 3
14 9
2 14
16 14
0 3
13 2
1 13
10 1
12 1
7 10
4 7
5 7
15 5

output:

15 11 5 8 4 6 7 0 12 3 10 16 1 9 13 14 2

result:

ok correct

Subtask #5:

score: 0
Accepted

Test #20:

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

input:

18 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8

output:

14 17 13 16 12 15 11 10 6 9 5 8 2 7 4 3 0 1

result:

ok correct

Test #21:

score: 0
Accepted
time: 2ms
memory: 3844kb

input:

27 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12

output:

26 22 25 21 24 20 23 19 14 18 13 17 12 16 11 15 6 10 5 9 8 2 7 4 3 0 1

result:

ok correct

Test #22:

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

input:

31 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14

output:

22 30 21 29 20 28 19 27 18 26 17 25 16 24 15 23 10 14 9 13 8 12 7 11 4 6 3 5 1 2 0

result:

ok correct

Test #23:

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

input:

500 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26
...

output:

499 382 498 381 497 380 496 379 495 378 494 377 493 376 492 375 491 374 490 373 489 372 488 371 487 370 486 369 485 368 484 367 483 366 482 365 481 364 480 363 479 362 478 361 477 360 476 359 475 358 474 357 473 356 472 355 471 354 470 353 469 352 468 351 467 350 466 349 465 348 464 347 463 346 462 ...

result:

ok correct

Test #24:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

33 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15

output:

30 32 29 31 28 22 27 21 26 20 25 19 24 18 23 17 14 16 13 15 12 10 11 9 6 8 5 7 2 4 0 3 1

result:

ok correct

Test #25:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

119 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26
...

output:

118 94 117 93 116 92 115 91 114 90 113 89 112 88 111 87 110 86 109 85 108 84 107 83 106 82 105 81 104 80 103 79 102 78 101 77 100 76 99 75 98 74 97 73 96 72 95 71 62 70 61 69 60 68 59 67 58 66 57 65 56 64 55 63 54 46 53 45 52 44 51 43 50 42 49 41 48 40 47 39 30 38 29 37 28 36 27 35 26 34 25 33 24 32...

result:

ok correct

Test #26:

score: 0
Accepted
time: 2ms
memory: 3828kb

input:

174 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26
...

output:

126 173 125 172 124 171 123 170 122 169 121 168 120 167 119 166 118 165 117 164 116 163 115 162 114 161 113 160 112 159 111 158 110 157 109 156 108 155 107 154 106 153 105 152 104 151 103 150 102 149 101 148 100 147 99 146 98 145 97 144 96 143 95 142 62 141 61 140 60 139 59 138 58 137 57 136 56 135 ...

result:

ok correct

Subtask #6:

score: 0
Accepted

Test #27:

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

input:

18 400000
7 6
8 7
5 8
4 5
3 4
9 3
10 11
12 10
13 12
14 13
9 14
2 9
15 2
16 15
17 16
1 17
0 1

output:

6 0 11 7 1 10 17 8 16 12 5 15 13 4 14 3 2 9

result:

ok correct

Test #28:

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

input:

500 400000
8 7
9 8
9 10
11 9
13 12
13 14
15 13
15 16
11 15
17 11
20 19
20 21
18 20
22 18
24 23
24 25
26 24
28 27
26 28
22 26
17 22
29 17
30 31
32 30
33 34
32 33
35 32
37 36
38 39
37 38
35 37
40 35
29 40
41 29
42 41
43 42
45 44
45 46
47 45
49 48
49 50
47 49
51 47
53 52
53 54
55 53
57 56
57 58
55 57
5...

output:

499 488 498 486 0 483 497 481 496 479 495 474 210 472 208 466 206 464 204 462 200 460 198 456 196 454 194 452 192 450 190 448 188 446 186 443 184 441 182 439 180 437 178 435 176 433 174 431 172 429 170 427 166 425 164 423 162 421 160 419 158 417 156 415 154 413 152 411 148 409 146 407 144 405 142 40...

result:

ok correct

Test #29:

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

input:

59 400000
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 49
51 50
52 ...

output:

0 58 1 57 2 56 3 55 4 54 5 53 6 52 7 51 8 50 9 49 10 48 11 47 12 46 13 45 14 44 15 43 16 42 17 41 18 40 19 39 20 38 21 37 22 36 23 35 24 34 25 33 26 32 27 31 28 30 29

result:

ok correct

Test #30:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

204 400000
13 12
13 14
15 13
16 17
15 16
18 15
20 19
20 21
22 20
23 24
22 23
18 22
11 18
25 11
26 25
27 26
28 27
10 28
9 10
8 9
7 8
29 7
32 31
30 32
29 30
33 29
6 33
34 6
35 34
5 35
36 5
4 36
37 4
48 47
48 49
50 48
51 50
53 52
54 53
56 55
54 56
51 54
57 51
59 58
59 60
61 59
63 62
61 63
64 61
66 65
6...

output:

24 195 21 193 19 191 17 189 14 187 12 185 23 183 20 179 16 176 13 173 22 170 15 168 18 166 11 164 25 162 26 160 27 158 70 156 67 151 65 149 62 147 60 145 58 140 55 138 52 136 49 134 47 131 28 129 69 126 66 122 63 120 59 116 56 114 53 112 48 110 10 108 68 106 61 104 54 101 50 99 31 97 9 95 64 93 51 9...

result:

ok correct

Test #31:

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

input:

273 400000
15 14
15 16
17 15
19 18
19 20
17 19
21 17
23 22
23 24
25 23
21 25
26 21
28 27
28 29
30 28
32 31
32 33
30 32
34 30
36 35
36 37
38 36
40 39
40 41
38 40
34 38
26 34
13 26
42 13
43 42
12 43
11 12
10 11
44 10
9 44
45 9
46 47
45 46
8 45
48 8
50 51
49 50
52 49
48 52
7 48
6 7
53 6
58 59
60 58
61 ...

output:

262 152 260 150 258 148 256 146 254 144 252 142 250 140 248 138 246 136 244 134 242 132 240 130 235 128 233 126 231 124 229 122 227 119 225 117 223 115 221 113 217 111 215 109 213 107 209 105 207 103 205 101 202 99 200 96 198 94 195 92 192 87 190 85 188 83 184 81 264 79 261 77 257 72 253 65 249 62 2...

result:

ok correct

Test #32:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

136 400000
19 18
19 20
17 19
16 17
15 16
14 15
21 14
22 21
13 22
23 13
12 23
24 12
11 24
10 11
9 10
8 9
7 8
6 7
25 6
26 25
5 26
4 5
27 4
28 27
29 28
40 39
40 41
42 40
44 43
44 45
42 44
46 42
47 48
49 47
51 50
51 52
49 51
46 49
53 46
55 54
56 55
57 56
58 59
60 58
62 61
62 63
60 62
57 60
53 57
64 53
6...

output:

20 125 18 123 19 120 17 118 16 114 15 112 14 109 21 107 22 105 13 102 23 100 12 98 24 96 11 94 10 91 9 89 8 87 7 85 6 83 25 81 26 79 0 74 5 71 1 69 135 67 4 65 27 63 2 61 28 59 3 54 29 52 134 50 30 48 31 45 133 43 132 41 131 39 32 124 130 121 129 117 33 115 128 111 34 108 127 104 75 101 70 97 66 93 ...

result:

ok correct

Subtask #7:

score: 0
Accepted

Test #33:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

500 400000
33 414
398 33
254 398
400 254
376 400
302 376
466 302
362 466
301 362
267 301
417 267
413 417
14 413
305 14
353 305
83 353
227 83
57 227
446 57
406 446
154 406
336 154
195 336
405 195
264 405
76 264
203 76
459 203
178 459
72 178
296 72
488 296
404 488
60 404
156 60
393 156
108 393
216 108...

output:

414 212 33 88 398 124 254 399 400 190 376 10 302 366 466 234 362 432 301 28 267 188 417 237 413 64 14 268 305 39 353 349 83 345 227 125 57 70 446 276 406 420 154 369 336 48 195 211 405 482 264 8 76 22 203 487 459 9 178 230 72 339 296 95 488 340 404 50 60 102 156 174 393 47 108 461 216 424 106 181 31...

result:

ok correct

Test #34:

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

input:

500 400000
243 472
21 472
171 243
31 243
419 21
366 21
474 171
246 171
363 31
201 31
317 419
458 419
59 366
7 366
417 474
394 474
351 246
191 246
431 363
202 363
397 201
81 201
28 317
237 317
71 458
221 458
239 59
429 59
0 7
60 7
418 417
18 417
240 394
341 394
440 351
485 351
373 191
487 191
261 431...

output:

498 497 494 495 481 493 476 491 461 488 460 484 452 483 439 480 436 478 434 473 433 470 428 466 427 465 426 463 421 459 420 447 414 443 413 425 412 423 410 422 409 415 408 411 404 407 400 405 389 403 388 398 381 395 367 393 364 392 356 391 353 385 352 383 346 382 345 378 339 376 337 375 327 372 325 ...

result:

ok correct

Test #35:

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

input:

500 400000
207 176
385 207
343 385
196 343
261 196
50 261
481 343
295 176
148 207
34 176
144 34
72 481
24 295
351 24
84 351
329 84
25 84
134 25
286 134
11 329
321 11
121 286
428 121
475 121
170 475
362 428
412 24
234 351
123 234
299 234
405 196
64 405
297 72
13 297
472 13
332 72
65 332
218 362
46 14...

output:

444 45 48 377 472 195 139 26 241 356 65 289 13 273 365 450 332 330 297 125 206 477 64 473 50 395 415 175 405 456 284 340 261 406 221 374 72 308 481 191 426 53 224 457 196 358 146 344 132 333 102 266 49 167 343 165 259 73 239 489 202 411 105 408 47 372 46 306 447 265 420 249 385 222 150 78 148 485 14...

result:

ok correct

Test #36:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

113 400000
78 45
67 45
40 67
25 40
54 67
3 54
44 54
70 3
15 25
37 15
11 15
27 11
102 37
110 102
97 110
41 97
31 41
9 11
24 9
87 24
46 24
84 46
109 46
95 27
49 97
101 49
71 49
94 41
29 25
55 29
99 55
22 55
17 99
33 17
75 33
60 33
32 70
63 32
88 63
39 32
51 39
36 88
57 51
19 57
65 19
50 65
26 51
43 26...

output:

106 62 30 58 10 81 61 104 6 68 0 92 80 91 2 69 42 38 1 28 56 83 76 79 59 23 96 108 4 86 82 50 66 21 111 7 77 100 14 73 64 72 48 65 16 52 103 43 98 19 47 57 8 36 112 26 105 88 93 51 85 63 18 39 107 75 89 60 5 32 90 70 20 33 74 109 34 84 13 78 12 44 35 17 53 3 101 99 94 87 71 54 31 46 49 45 41 22 97 9...

result:

ok correct

Test #37:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

479 400000
217 361
375 361
370 217
138 217
393 138
297 138
263 297
119 263
202 119
247 202
376 247
285 376
101 285
236 101
351 285
409 351
197 409
11 236
97 11
122 409
189 122
391 189
232 391
88 391
160 197
272 160
313 272
335 313
14 97
193 88
410 193
116 193
348 11
341 348
281 335
198 281
455 410
4...

output:

388 306 67 468 149 439 73 415 363 37 93 469 372 460 109 252 378 170 276 68 65 222 242 162 102 124 259 84 133 362 29 324 441 307 151 179 258 432 176 403 371 209 296 167 268 22 142 464 99 434 472 381 412 79 233 16 126 128 111 54 39 31 303 369 274 42 256 419 205 360 141 315 13 219 451 422 235 264 156 2...

result:

ok correct

Test #38:

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

input:

269 400000
75 180
56 180
78 180
231 75
127 231
244 127
16 244
113 16
178 113
85 16
20 85
74 20
249 74
134 249
248 249
96 134
109 74
17 109
164 96
32 109
265 32
253 265
120 265
82 120
4 253
28 4
150 28
53 120
165 53
137 53
31 137
206 31
123 206
102 123
168 17
33 168
174 253
162 174
243 174
193 243
10...

output:

130 102 77 123 222 78 214 56 5 206 241 180 230 193 1 150 242 75 71 31 10 243 8 231 197 165 118 162 52 137 34 28 218 178 194 174 156 127 73 82 49 53 263 4 181 253 105 244 57 120 11 113 233 33 224 265 175 168 51 16 255 85 185 32 151 17 84 109 39 20 264 248 259 74 187 249 114 134 112 177 92 96 63 192 1...

result:

ok correct

Test #39:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

347 400000
305 85
97 305
161 97
125 161
200 125
317 200
140 317
211 140
88 161
174 88
256 174
135 256
148 135
272 148
116 272
269 116
228 272
131 228
141 131
327 135
232 327
43 232
191 43
313 191
80 313
150 80
214 150
23 214
126 80
215 126
10 215
156 10
1 156
79 10
284 79
114 284
316 156
335 316
119...

output:

268 211 165 140 55 317 328 85 90 305 281 200 242 141 234 125 221 97 189 269 245 161 219 131 206 228 183 116 46 88 11 272 9 174 338 256 322 148 177 135 170 327 134 232 20 43 323 23 308 273 262 214 199 191 182 169 168 122 107 313 28 222 343 187 324 150 288 334 236 152 180 114 159 80 157 284 146 171 84...

result:

ok correct

Test #40:

score: 0
Accepted
time: 2ms
memory: 3848kb

input:

189 400000
101 23
8 101
123 8
24 123
134 123
119 134
2 134
105 2
161 105
72 161
126 72
53 126
9 53
138 9
188 53
98 188
136 98
78 136
69 98
4 78
66 4
145 66
91 66
132 91
49 188
17 49
87 138
154 87
184 91
131 184
108 131
3 108
56 184
183 108
62 183
173 62
0 173
185 173
110 185
164 110
83 164
135 62
46...

output:

128 92 150 23 68 179 47 155 159 125 143 101 107 186 35 169 176 102 80 41 76 24 44 8 25 165 1 123 158 119 156 71 153 51 93 45 11 181 106 171 77 168 75 166 64 139 172 134 160 112 141 99 19 97 157 95 149 79 146 58 57 177 42 147 163 142 152 48 117 29 115 20 109 12 40 2 170 182 113 154 103 127 81 105 74 ...

result:

ok correct

Subtask #8:

score: 0
Accepted

Test #41:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

501 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26
...

output:

500 382 499 381 498 380 497 379 496 378 495 377 494 376 493 375 492 374 491 373 490 372 489 371 488 370 487 369 486 368 485 367 484 366 483 365 482 364 481 363 480 362 479 361 478 360 477 359 476 358 475 357 474 356 473 355 472 354 471 353 470 352 469 351 468 350 467 349 466 348 465 347 464 346 463 ...

result:

ok correct

Test #42:

score: 0
Accepted
time: 52ms
memory: 12368kb

input:

58961 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 2...

output:

58960 49150 58959 49149 58958 49148 58957 49147 58956 49146 58955 49145 58954 49144 58953 49143 58952 49142 58951 49141 58950 49140 58949 49139 58948 49138 58947 49137 58946 49136 58945 49135 58944 49134 58943 49133 58942 49132 58941 49131 58940 49130 58939 49129 58938 49128 58937 49127 58936 49126 ...

result:

ok correct

Test #43:

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

input:

511 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26
...

output:

382 510 381 509 380 508 379 507 378 506 377 505 376 504 375 503 374 502 373 501 372 500 371 499 370 498 369 497 368 496 367 495 366 494 365 493 364 492 363 491 362 490 361 489 360 488 359 487 358 486 357 485 356 484 355 483 354 482 353 481 352 480 351 479 350 478 349 477 348 476 347 475 346 474 345 ...

result:

ok correct

Test #44:

score: 0
Accepted
time: 79ms
memory: 18868kb

input:

100000 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 ...

output:

99999 98302 99998 98301 99997 98300 99996 98299 99995 98298 99994 98297 99993 98296 99992 98295 99991 98294 99990 98293 99989 98292 99988 98291 99987 98290 99986 98289 99985 98288 99984 98287 99983 98286 99982 98285 99981 98284 99980 98283 99979 98282 99978 98281 99977 98280 99976 98279 99975 98278 ...

result:

ok correct

Test #45:

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

input:

887 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26
...

output:

886 766 885 765 884 764 883 763 882 762 881 761 880 760 879 759 878 758 877 757 876 756 875 755 874 754 873 753 872 752 871 751 870 750 869 749 868 748 867 747 866 746 865 745 864 744 863 743 862 742 861 741 860 740 859 739 858 738 857 737 856 736 855 735 854 734 853 733 852 732 851 731 850 730 849 ...

result:

ok correct

Test #46:

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

input:

2027 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26...

output:

2026 1534 2025 1533 2024 1532 2023 1531 2022 1530 2021 1529 2020 1528 2019 1527 2018 1526 2017 1525 2016 1524 2015 1523 2014 1522 2013 1521 2012 1520 2011 1519 2010 1518 2009 1517 2008 1516 2007 1515 2006 1514 2005 1513 2004 1512 2003 1511 2002 1510 2001 1509 2000 1508 1999 1507 1998 1506 1997 1505 ...

result:

ok correct

Test #47:

score: 0
Accepted
time: 0ms
memory: 4148kb

input:

3070 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26...

output:

2046 3069 2045 3068 2044 3067 2043 3066 2042 3065 2041 3064 2040 3063 2039 3062 2038 3061 2037 3060 2036 3059 2035 3058 2034 3057 2033 3056 2032 3055 2031 3054 2030 3053 2029 3052 2028 3051 2027 3050 2026 3049 2025 3048 2024 3047 2023 3046 2022 3045 2021 3044 2020 3043 2019 3042 2018 3041 2017 3040 ...

result:

ok correct

Test #48:

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

input:

6956 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 26...

output:

6955 6142 6954 6141 6953 6140 6952 6139 6951 6138 6950 6137 6949 6136 6948 6135 6947 6134 6946 6133 6945 6132 6944 6131 6943 6130 6942 6129 6941 6128 6940 6127 6939 6126 6938 6125 6937 6124 6936 6123 6935 6122 6934 6121 6933 6120 6932 6119 6931 6118 6930 6117 6929 6116 6928 6115 6927 6114 6926 6113 ...

result:

ok correct

Test #49:

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

input:

13690 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 2...

output:

13689 12286 13688 12285 13687 12284 13686 12283 13685 12282 13684 12281 13683 12280 13682 12279 13681 12278 13680 12277 13679 12276 13678 12275 13677 12274 13676 12273 13675 12272 13674 12271 13673 12270 13672 12269 13671 12268 13670 12267 13669 12266 13668 12265 13667 12264 13666 12263 13665 12262 ...

result:

ok correct

Test #50:

score: 0
Accepted
time: 14ms
memory: 6084kb

input:

18091 400000
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
19 9
20 9
21 10
22 10
23 11
24 11
25 12
26 12
27 13
28 13
29 14
30 14
31 15
32 15
33 16
34 16
35 17
36 17
37 18
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
47 23
48 23
49 24
50 24
51 25
52 25
53 2...

output:

16382 18090 16381 18089 16380 18088 16379 18087 16378 18086 16377 18085 16376 18084 16375 18083 16374 18082 16373 18081 16372 18080 16371 18079 16370 18078 16369 18077 16368 18076 16367 18075 16366 18074 16365 18073 16364 18072 16363 18071 16362 18070 16361 18069 16360 18068 16359 18067 16358 18066 ...

result:

ok correct

Subtask #9:

score: 0
Accepted

Test #51:

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

input:

1000 400000
6 5
7 8
6 7
9 6
11 10
11 12
13 11
14 15
13 14
9 13
16 9
18 17
18 19
20 18
22 21
22 23
20 22
24 20
26 25
26 27
28 26
30 29
30 31
28 30
24 28
16 24
32 16
33 32
35 34
35 36
37 35
39 38
39 40
37 39
41 37
43 42
43 44
45 43
47 46
47 48
45 47
41 45
49 41
50 51
52 50
54 53
54 55
52 54
56 52
58 5...

output:

448 989 446 987 444 985 442 983 440 981 438 979 436 977 434 975 432 969 430 966 428 964 426 961 424 959 422 956 420 951 414 949 412 946 410 944 408 942 406 940 404 938 402 936 400 934 398 932 396 930 391 928 389 925 385 923 383 921 381 919 379 917 357 913 355 911 353 909 351 907 349 905 347 903 345 ...

result:

ok correct

Test #52:

score: 0
Accepted
time: 11ms
memory: 4900kb

input:

10000 400000
7 6
7 8
9 7
11 10
11 12
9 11
13 9
15 14
15 16
17 15
19 18
19 20
17 19
13 17
21 13
23 22
23 24
25 23
27 26
27 28
25 27
29 25
30 31
32 30
34 33
34 35
32 34
29 32
21 29
36 21
38 37
38 39
40 38
42 41
42 43
40 42
44 40
46 45
46 47
48 46
50 49
50 51
48 50
44 48
52 44
54 53
54 55
56 54
58 57
5...

output:

9981 7491 9979 7489 9977 7486 9975 7484 9973 7482 9971 7480 9969 7478 9967 7476 9964 7474 9962 7472 9960 7470 9958 7468 9956 7466 9954 7464 9952 7462 9948 7460 9946 7458 9943 7456 9941 7454 9936 7452 9934 7450 9932 7448 9930 7446 9928 7444 9926 7442 9924 7440 9922 7438 9919 7436 9915 7434 9912 7431 ...

result:

ok correct

Test #53:

score: 0
Accepted
time: 96ms
memory: 18728kb

input:

100000 400000
10 9
10 11
12 10
14 13
14 15
12 14
16 12
18 17
18 19
20 18
22 21
22 23
20 22
16 20
24 16
26 25
26 27
28 26
30 29
30 31
28 30
32 28
34 33
34 35
36 34
38 37
38 39
36 38
32 36
24 32
40 24
42 41
42 43
44 42
46 45
46 47
44 46
48 44
50 49
50 51
52 50
54 53
54 55
52 54
48 52
56 48
58 57
58 59...

output:

99989 81210 99987 81208 99985 81206 99983 81204 99981 81202 99979 81200 99977 81198 99975 81196 99973 81194 99971 81192 99969 81190 99967 81188 99965 81186 99963 81184 99961 81182 99959 81180 99957 81178 99955 81176 99953 81174 99951 81172 99949 81170 99947 81168 99945 81166 99943 81164 99941 81162 ...

result:

ok correct

Test #54:

score: 0
Accepted
time: 82ms
memory: 19148kb

input:

98793 400000
7 6
7 8
9 7
11 10
11 12
9 11
13 9
15 14
15 16
17 15
19 18
19 20
17 19
13 17
21 13
23 22
23 24
25 23
27 26
27 28
25 27
29 25
31 30
31 32
33 31
35 34
35 36
33 35
29 33
21 29
37 21
39 38
39 40
41 39
43 42
43 44
41 43
45 41
47 46
47 48
49 47
51 50
51 52
49 51
45 49
53 45
55 54
55 56
57 55
5...

output:

98785 52963 98783 52961 98781 52959 98779 52957 98776 52955 98774 52953 98772 52951 98770 52949 98768 52947 98766 52945 98764 52943 98762 52941 98760 52939 98758 52937 98756 52935 98754 52933 98752 52931 98750 52929 98748 52927 98746 52925 98744 52923 98742 52921 98740 52919 98738 52917 98736 52915 ...

result:

ok correct

Test #55:

score: 0
Accepted
time: 21ms
memory: 7120kb

input:

24452 400000
9 8
9 10
11 9
13 12
13 14
11 13
15 11
17 16
17 18
19 17
21 20
21 22
19 21
15 19
23 15
25 24
25 26
27 25
29 28
29 30
27 29
31 27
33 32
33 34
35 33
37 36
37 38
35 37
31 35
23 31
39 23
41 40
41 42
43 41
45 44
45 46
43 45
47 43
49 48
49 50
51 49
53 52
53 54
51 53
47 51
55 47
57 56
57 58
59 ...

output:

24451 12668 24444 12666 24442 12664 24440 12662 24438 12660 24436 12658 24434 12656 24432 12654 24430 12652 24428 12650 24426 12648 24424 12646 24422 12644 24420 12642 24418 12640 24416 12638 24414 12636 24412 12634 24410 12632 24408 12630 24406 12628 24404 12626 24402 12624 24400 12622 24398 12620 ...

result:

ok correct

Test #56:

score: 0
Accepted
time: 34ms
memory: 10496kb

input:

46432 400000
6 5
6 7
8 6
10 9
10 11
8 10
12 8
14 13
14 15
16 14
18 17
16 18
12 16
19 12
21 20
21 22
23 21
25 24
25 26
23 25
27 23
29 28
29 30
31 29
33 32
33 34
31 33
27 31
19 27
35 19
37 36
37 38
39 37
41 40
41 42
39 41
43 39
45 44
45 46
47 45
49 48
49 50
47 49
43 47
51 43
53 52
53 54
55 53
57 56
57...

output:

46421 31373 46419 31371 46417 31369 46415 31367 46413 31365 46411 31363 46409 31361 46407 31359 46405 31357 46403 31354 46401 31352 46399 31350 46397 31348 46395 31345 46393 31342 46391 31340 46389 31338 46387 31335 46385 31333 46383 31330 46381 31328 46379 31326 46377 31324 46375 31322 46373 31320 ...

result:

ok correct

Test #57:

score: 0
Accepted
time: 76ms
memory: 15548kb

input:

77532 400000
8 7
8 9
10 8
12 11
12 13
10 12
14 10
16 15
16 17
18 16
20 19
20 21
18 20
14 18
22 14
24 23
24 25
26 24
28 27
28 29
26 28
30 26
32 31
32 33
34 32
36 35
36 37
34 36
30 34
22 30
38 22
40 39
40 41
42 40
44 43
44 45
42 44
46 42
48 47
48 49
50 48
52 51
52 53
50 52
46 50
54 46
56 55
56 57
58 5...

output:

36728 77523 36726 77521 36724 77519 36722 77517 36720 77515 36718 77513 36716 77511 36714 77509 36712 77507 36710 77505 36708 77503 36706 77501 36704 77499 36702 77497 36699 77495 36697 77493 36695 77491 36693 77489 36691 77487 36688 77485 36686 77483 36684 77481 36681 77479 36679 77477 36677 77475 ...

result:

ok correct

Test #58:

score: 0
Accepted
time: 2ms
memory: 4224kb

input:

4093 400000
12 11
12 13
14 12
16 15
14 16
17 14
18 19
20 18
22 21
22 23
20 22
17 20
24 17
26 25
26 27
28 26
30 29
30 31
28 30
32 28
34 33
34 35
36 34
38 37
38 39
36 38
32 36
24 32
40 24
42 41
42 43
44 42
44 45
46 44
47 48
49 47
51 50
51 52
49 51
46 49
53 46
55 54
55 56
57 55
59 58
59 60
57 59
61 57
...

output:

4081 3368 4079 3366 4077 3364 4075 3362 4073 3359 4071 3357 4069 3353 4067 3351 4065 3348 4062 3346 4060 3344 4058 3342 4056 3340 4054 3338 4031 3336 4028 3334 4026 3332 4022 3329 4020 3327 4018 3325 4016 3323 4013 3321 4011 3319 4009 3317 4007 3315 4005 3313 4003 3311 4001 3309 3999 3307 3997 3305 ...

result:

ok correct

Subtask #10:

score: 0
Accepted

Test #59:

score: 0
Accepted
time: 110ms
memory: 19916kb

input:

99999 400000
11681 58292
11681 63929
49752 11681
30596 74400
30596 39261
49752 30596
19390 49752
89694 31923
19390 89694
54297 19390
42389 12902
42389 60328
72803 42389
69881 43761
69881 95741
72803 69881
96271 72803
63872 20658
63872 93588
35833 63872
48418 44153
35833 48418
96271 35833
54297 96271...

output:

99998 99984 99994 99976 99993 99975 99992 99972 99988 99971 99986 99966 99985 99962 99980 99960 99973 99956 99970 99955 99964 99951 99963 99943 99959 99942 99954 99934 99952 99932 99946 99928 99945 99927 99944 99925 99941 99922 99940 99921 99933 99920 99930 99918 99929 99915 99926 99914 99923 99912 ...

result:

ok correct

Test #60:

score: 0
Accepted
time: 190ms
memory: 24668kb

input:

99999 400000
22911 42906
55177 22911
45848 55177
42077 45848
72422 42077
18572 72422
32391 18572
50776 32391
37509 50776
1803 37509
22729 1803
59931 22729
86437 59931
75596 86437
97533 75596
84264 97533
79370 84264
73290 79370
17059 73290
60073 17059
604 60073
89686 604
45405 89686
1176 45405
25995 ...

output:

51189 47838 98765 35392 10953 24097 74641 86378 63142 64069 12491 63565 15883 41516 29984 81204 96124 24446 7825 57155 44605 38765 8178 83778 12111 80741 8868 38750 62058 9034 10292 55306 29953 74995 631 8781 42499 42162 60664 33045 90314 4539 70754 8531 74033 30489 4047 69102 3482 44685 54859 52236...

result:

ok correct

Test #61:

score: 0
Accepted
time: 115ms
memory: 19828kb

input:

100000 400000
35357 73932
35357 71898
53297 35357
20900 39284
20900 36611
53297 20900
24574 53297
3496 19078
3496 63896
60776 3496
51617 31031
51617 73962
60776 51617
24574 60776
41273 24574
2824 85006
2824 22935
88300 2824
21588 95516
21588 81144
88300 21588
1650 88300
68562 25267
68562 31658
62356...

output:

99999 99998 99973 99996 99963 99993 99956 99990 99955 99978 99953 99974 99952 99962 99947 99960 99946 99959 99941 99950 99934 99942 99929 99940 99928 99938 99926 99936 99924 99922 99921 99907 99912 99903 99906 99900 99905 99899 99895 99891 99892 99883 99888 99880 99886 99879 99881 99874 99877 99870 ...

result:

ok correct

Test #62:

score: 0
Accepted
time: 127ms
memory: 23632kb

input:

100000 400000
49749 56050
49749 40208
54907 49749
38195 98216
38195 14892
54907 38195
56213 54907
53116 48113
53116 80410
17137 53116
23663 52076
23663 81699
17137 23663
56213 17137
26079 56213
91162 31575
91162 87334
39593 91162
1938 59342
1938 19586
39593 1938
77110 39593
53644 54722
53644 51522
7...

output:

56161 99997 7628 99995 61213 99992 34331 99985 64120 99984 69214 99981 3621 99971 15524 99969 33060 99968 44985 99966 79185 99960 51845 99951 1092 99948 75372 99946 81319 99944 49149 99940 91382 99939 14464 99937 66598 99932 53774 99928 60636 99927 21308 99925 24991 99921 50593 99918 84728 99914 554...

result:

ok correct

Test #63:

score: 0
Accepted
time: 153ms
memory: 22812kb

input:

100000 400000
9655 96550
75626 9655
54376 75626
11841 54376
73169 11841
41885 73169
84310 41885
12127 84310
19301 12127
70458 38257
5041 70458
84680 5041
50387 84680
73867 50387
11702 73867
89735 11702
29414 89735
75189 29414
41008 75189
39369 41008
43391 39369
6443 43391
4723 6443
24708 4723
48499 ...

output:

38257 99989 70458 99988 5041 99983 84680 99980 50387 99975 73867 99973 11702 99972 89735 99971 29414 99964 75189 99963 41008 99962 39369 99961 43391 99957 6443 99956 4723 99952 24708 99944 48499 99936 58708 99935 90323 99930 40282 99927 90401 99926 63104 99924 87927 99923 29496 99921 4641 99920 8220...

result:

ok correct

Test #64:

score: 0
Accepted
time: 142ms
memory: 23096kb

input:

100000 400000
85640 47421
88305 85640
5714 88305
12158 5714
21045 12158
4595 21045
59201 4595
70325 59201
12459 70325
75946 12459
59593 75946
73653 59593
36224 73653
37034 36224
11349 37034
78127 11349
80935 78127
44355 80935
50188 44355
6163 50188
35432 6163
32717 35432
44709 32717
20567 44709
6362...

output:

83961 99992 37115 99988 6830 99983 20166 99982 22010 99980 65522 99975 34999 99970 73277 99965 44759 99960 4456 99957 50254 99955 58018 99953 51236 99952 3907 99950 99753 99946 7524 99944 61002 99942 56145 99935 93290 99930 96427 99925 8591 99923 28331 99921 2056 99916 2602 99915 26459 99914 64873 9...

result:

ok correct

Test #65:

score: 0
Accepted
time: 168ms
memory: 24332kb

input:

100000 400000
68192 59977
99869 68192
79880 99869
85798 79880
65433 85798
25657 65433
81982 25657
1785 81982
86793 1785
92930 86793
97721 92930
85396 97721
47062 85396
84379 47062
51598 84379
79308 51598
16011 79308
99639 16011
29146 99639
55098 29146
40431 55098
33646 40431
60840 33646
2163 60840
8...

output:

56018 14554 76072 42642 70976 24377 42693 3665 94200 9777 35394 38577 1509 32408 95319 7568 45951 17538 72212 31317 61530 38472 456 2720 50047 60256 63149 29748 90292 56901 59148 72348 25058 54445 43830 24436 59375 11885 70122 77140 24157 37972 78603 15456 66685 64040 18760 63832 88172 55317 90402 2...

result:

ok correct

Test #66:

score: 0
Accepted
time: 113ms
memory: 19592kb

input:

100000 400000
67858 63179
67858 60149
74375 67858
57708 13959
57708 45053
74375 57708
90549 74375
95708 88814
95708 47964
94504 95708
19427 84873
19427 5912
94504 19427
90549 94504
55452 90549
5889 92006
5889 26256
6130 5889
37782 41675
37782 80036
6130 37782
5068 6130
68617 81486
68617 39080
19381 ...

output:

99996 99999 99994 99998 99988 99997 99986 99993 99984 99987 99981 99983 99978 99979 99977 99973 99976 99960 99972 99959 99970 99956 99967 99955 99966 99954 99963 99944 99958 99943 99923 99939 99918 99933 99916 99932 99913 99926 99899 99925 99886 99924 99879 99917 99874 99911 99870 99906 99868 99904 ...

result:

ok correct

Test #67:

score: 0
Accepted
time: 134ms
memory: 23892kb

input:

100000 400000
38314 97507
38314 37025
91153 38314
8519 9825
8519 1911
91153 8519
35444 91153
97524 48140
97524 81881
2370 97524
6135 77571
6135 89643
2370 6135
35444 2370
40772 35444
21728 57143
21728 12712
80043 21728
95691 79282
80043 95691
93628 80043
3661 35183
72076 3661
7018 80806
7018 30247
7...

output:

53093 99993 92839 99989 42556 99978 17644 99977 6083 99970 71109 99967 61350 99956 78404 99949 4556 99948 75756 99937 27708 99930 21975 99928 41110 99927 9879 99926 29242 99920 97069 99916 84773 99913 84324 99909 44249 99894 39393 99892 84321 99890 68709 99884 51257 99868 56231 99864 12980 99862 384...

result:

ok correct

Test #68:

score: 0
Accepted
time: 128ms
memory: 24052kb

input:

100000 400000
67585 35704
28722 67585
10112 28722
88548 10112
54253 88548
73133 54253
42287 73133
13364 42287
98176 13364
13394 6776
48919 13394
90568 48919
89149 90568
89172 89149
49551 89172
11410 49551
65186 11410
80867 65186
36623 80867
94769 36623
20810 94769
81487 20810
324 81487
57414 324
347...

output:

6776 99993 13394 99988 48919 99985 90568 99983 89149 99979 89172 99973 49551 99961 11410 99960 65186 99953 80867 99946 36623 99943 94769 99937 20810 99934 81487 99930 324 99923 57414 99922 34734 99921 18030 99920 93824 99908 56085 99901 96075 99891 32774 99874 18750 99868 20004 99864 94295 99863 317...

result:

ok correct

Test #69:

score: 0
Accepted
time: 143ms
memory: 23420kb

input:

100000 400000
6549 88281
89934 6549
87980 89934
95330 87980
1402 95330
73144 1402
92562 73144
84778 92562
76427 84778
15252 76427
18967 15252
11354 18967
27410 11354
32717 27410
6426 32717
32969 6426
50931 32969
63720 50931
38918 63720
94868 38918
54886 94868
65899 54886
48760 65899
39800 48760
6935...

output:

99998 61196 99990 46126 99986 34735 99981 88559 99976 95731 99975 59705 99968 69112 99946 13909 99945 2015 99944 80875 99943 78237 99938 7080 99936 15079 99932 69603 99931 80753 99919 77794 99916 21446 99915 43799 99912 27197 99910 39038 99909 16233 99904 28621 99900 34881 99899 26861 99892 81321 99...

result:

ok correct

Test #70:

score: 0
Accepted
time: 134ms
memory: 21968kb

input:

99999 400000
64820 1287
64820 78874
37336 64820
28991 6921
28991 54104
37336 28991
70307 37336
31466 5785
31466 13812
6130 31466
32923 18164
32923 74699
6130 32923
70307 6130
91444 70307
10557 71191
10557 93985
90010 10557
32148 48707
32148 38708
90010 32148
41939 90010
6652 75287
6652 3338
57249 66...

output:

88498 99997 29773 99992 52507 99987 77030 99977 73669 99975 38402 99970 9989 99967 40252 99965 40844 99958 15280 99955 26098 99950 88227 99943 26204 99942 25344 99941 16774 99940 88905 99937 55549 99934 60803 99930 90607 99911 22860 99888 42692 99886 29217 99882 86929 99880 18850 99876 13592 99875 9...

result:

ok correct

Test #71:

score: 0
Accepted
time: 177ms
memory: 24868kb

input:

100000 400000
87219 78817
59973 87219
6646 59973
87634 6646
4195 87634
13042 4195
41084 13042
67419 41084
50801 67419
66524 50801
53601 66524
45176 53601
79636 45176
46213 79636
57540 46213
43569 57540
69993 43569
7376 69993
12653 7376
80716 12653
86447 80716
49859 86447
71777 49859
57476 71777
4582...

output:

23492 46752 10639 55507 61368 29384 42049 4284 32809 92804 56673 91658 34183 22801 5221 86011 59628 71651 22686 86795 50281 72004 84602 9324 5697 52231 74386 13344 11724 38066 77349 73736 88394 28770 34684 30732 17687 65913 22466 70090 54755 42559 39117 37897 2442 13172 95382 53530 20831 38508 87069...

result:

ok correct

Test #72:

score: 0
Accepted
time: 154ms
memory: 24420kb

input:

100000 400000
83816 93354
90376 83816
25951 90376
97866 25951
2405 97866
314 2405
87136 314
31787 87136
4403 31787
91307 4403
89212 91307
26424 89212
90029 26424
82476 90029
14718 82476
92034 14718
78383 92034
65609 78383
99677 65609
80426 99677
97137 80426
16030 97137
62662 16030
73376 62662
64740 ...

output:

93354 91135 83816 12105 90376 50464 25951 92435 97866 20360 2405 15970 314 57547 87136 94024 31787 1227 4403 60826 91307 64104 89212 33579 26424 31387 90029 36362 82476 52181 14718 5095 92034 49165 78383 49403 65609 24138 99677 54752 80426 35275 97137 20991 16030 74782 62662 99887 73376 46737 64740 ...

result:

ok correct

Test #73:

score: 0
Accepted
time: 120ms
memory: 20184kb

input:

100000 400000
60633 14524
82214 14524
15014 60633
19923 60633
93596 82214
97182 82214
15820 15014
82989 15014
31656 19923
47686 19923
64549 93596
57903 93596
45519 97182
52236 97182
38856 15820
35427 15820
33438 82989
80651 82989
60083 31656
3711 31656
52887 47686
47060 47686
27987 64549
11470 64549...

output:

99759 99998 99711 99997 99598 99996 99594 99995 99350 99994 99317 99989 99272 99988 99268 99987 99200 99984 99133 99983 99122 99981 99076 99978 99047 99973 98898 99967 98885 99966 98859 99965 98828 99964 98810 99962 98749 99959 98738 99958 98707 99955 98676 99949 98630 99948 98424 99947 98390 99944 ...

result:

ok correct

Test #74:

score: 0
Accepted
time: 126ms
memory: 19584kb

input:

100000 400000
74551 52369
74551 14890
35856 74551
59091 25828
59091 21752
35856 59091
42833 35856
58418 88195
58418 59724
84165 58418
84836 32235
84836 65208
84165 84836
42833 84165
25273 42833
59085 66192
59085 29510
22738 59085
50833 12181
50833 11186
22738 50833
7684 22738
61414 3921
61414 24391
...

output:

99994 99997 99993 99996 99980 99995 99975 99990 99973 99989 99971 99988 99969 99984 99963 99977 99960 99967 99957 99965 99947 99958 99928 99949 99919 99948 99917 99945 99915 99944 99909 99939 99902 99935 99900 99933 99897 99932 99893 99922 99887 99913 99885 99912 99881 99910 99875 99906 99872 99904 ...

result:

ok correct

Test #75:

score: 0
Accepted
time: 139ms
memory: 19564kb

input:

100000 400000
23044 15768
10690 15768
66326 10690
47284 66326
88135 47284
13985 47284
80266 13985
94610 80266
5729 94610
65260 5729
27252 65260
90818 27252
35922 27252
80958 35922
66596 80958
40810 66596
94354 90818
4426 94354
87504 4426
17274 40810
20951 17274
90916 4426
5294 90916
61205 5294
10843...

output:

66690 43268 43921 9540 7829 93511 52944 61950 87197 92274 68751 51834 77654 18124 70806 95359 48855 32991 6474 22326 2388 95648 99943 94300 86524 69449 17872 34221 9157 33151 72400 27436 69664 79336 53711 74602 11819 54303 11317 48080 5547 47124 3234 20104 67736 13000 61311 96116 58266 91353 5849 72...

result:

ok correct

Test #76:

score: 0
Accepted
time: 55ms
memory: 10216kb

input:

42061 400000
40244 13586
24355 40244
37859 24355
38455 37859
21534 38455
41695 21534
6535 21534
39223 6535
33203 39223
36353 39223
23829 36353
26752 23829
6680 37859
36142 41695
31851 38455
15428 31851
34029 15428
6592 6680
2856 6592
28423 2856
3559 28423
1682 28423
14567 1682
2083 3559
33115 2856
2...

output:

23110 2752 31941 29615 26634 37122 40713 19083 20953 1539 10174 39913 29687 34677 4520 21982 31892 9837 8529 32936 19408 23858 17786 21556 41653 19649 21398 17710 14116 15218 38961 14482 27494 13983 19197 37684 9711 37130 33570 26679 22780 22969 22311 22404 12737 35826 460 28981 36184 25874 34862 23...

result:

ok correct

Test #77:

score: 0
Accepted
time: 115ms
memory: 19668kb

input:

100000 400000
18068 38447
18068 16704
12886 18068
96192 62000
96192 30182
12886 96192
20218 12886
4651 87356
4651 14959
2329 4651
24202 95450
24202 69280
2329 24202
20218 2329
82250 20218
9698 39454
9698 24527
54658 9698
22361 41123
22361 75075
54658 22361
75859 54658
2465 3431
2465 80791
82434 2465...

output:

99995 99999 99994 99998 99991 99996 99990 99989 99986 99988 99981 99987 99975 99982 99972 99980 99969 99978 99961 99977 99960 99976 99956 99966 99950 99955 99948 99951 99936 99947 99930 99946 99928 99943 99927 99941 99924 99940 99923 99939 99920 99938 99918 99933 99909 99932 99908 99929 99907 99919 ...

result:

ok correct

Test #78:

score: 0
Accepted
time: 179ms
memory: 24412kb

input:

100000 400000
49637 81421
49637 87418
41787 49637
36937 80516
36937 4482
41787 36937
81831 41787
17718 32843
17718 3123
34635 17718
68816 68762
68816 45362
34635 68816
81831 34635
58571 81831
97862 38151
97862 58848
68087 97862
98892 18847
98892 42817
68087 98892
70157 68087
49009 58911
49009 5740
1...

output:

2418 99999 90426 99996 29985 99993 64098 99988 16852 99986 71905 99985 69286 99983 58873 99982 99334 99980 42730 99979 72342 99978 55346 99972 5395 99970 56862 99961 48770 99960 62214 99948 66039 99946 29245 99931 99523 99925 23005 99915 11901 99912 33634 99909 32983 99907 39753 99904 34880 99891 11...

result:

ok correct

Test #79:

score: 0
Accepted
time: 145ms
memory: 23540kb

input:

100000 400000
2718 29077
2718 66694
33954 2718
63692 17313
63692 55977
33954 63692
92365 33954
15804 50226
15804 34164
15693 15804
41697 91959
41697 26716
15693 41697
92365 15693
4605 92365
94959 20195
94959 26611
40261 94959
84759 64237
84759 16046
40261 84759
41265 40261
73532 55347
73532 66262
17...

output:

53514 99997 30293 99996 60440 99995 11440 99987 76449 99985 87812 99984 20840 99977 3890 99976 19986 99971 52825 99965 86906 99957 70958 99954 40425 99949 35397 99946 39198 99945 55385 99944 22716 99943 75206 99939 8266 99934 26371 99929 45370 99926 5572 99925 13102 99917 12742 99916 57207 99913 326...

result:

ok correct

Test #80:

score: 0
Accepted
time: 131ms
memory: 20116kb

input:

99999 400000
26785 74388
26785 92533
54821 26785
82301 54821
35196 97901
35196 77127
50121 35196
82301 50121
91496 82301
83012 67595
47081 68432
83012 47081
13119 83012
9120 91371
9120 95312
84992 9120
20880 67102
84992 20880
13119 84992
91496 13119
48942 91496
31457 190
31457 97876
80767 31457
3153...

output:

99995 99991 99990 99988 99989 99987 99977 99985 99975 99984 99971 99983 99968 99980 99959 99978 99954 99976 99951 99969 99943 99966 99942 99962 99940 99961 99939 99960 99934 99957 99933 99948 99926 99941 99923 99937 99920 99935 99919 99931 99917 99930 99915 99928 99908 99921 99903 99910 99898 99899 ...

result:

ok correct

Test #81:

score: 0
Accepted
time: 154ms
memory: 22820kb

input:

99999 400000
73548 80634
73548 36217
5983 73548
20279 20643
20279 51170
5983 20279
86427 5983
40386 9234
40386 7815
55774 40386
4478 87265
4478 11861
55774 4478
86427 55774
58343 86427
64960 42247
64960 60439
54087 64960
60451 16071
60451 34163
54087 60451
68602 54087
60022 28944
60022 56619
39066 6...

output:

23300 99997 95178 99996 38128 99995 9117 99992 28474 99987 54147 99983 78591 99979 67273 99968 42563 99964 66261 99959 92336 99958 80803 99948 92492 99935 6374 99925 67681 99921 32700 99914 30172 99905 28005 99904 26162 99903 46176 99901 46631 99899 26744 99897 96865 99895 22149 99888 96927 99887 51...

result:

ok correct

Test #82:

score: 0
Accepted
time: 131ms
memory: 24344kb

input:

99999 400000
27083 34518
26907 27083
56011 26907
84232 56011
53004 84232
94462 53004
20753 94462
8923 20753
64585 8923
82723 34029
11457 82723
71040 11457
77504 71040
33858 77504
93550 33858
37588 93550
68071 37588
93068 68071
40821 93068
20440 40821
24231 20440
22353 24231
68281 22353
44162 68281
8...

output:

99993 34029 99979 82723 99970 11457 99968 71040 99965 77504 99959 33858 99957 93550 99954 37588 99952 68071 99951 93068 99947 40821 99945 20440 99943 24231 99940 22353 99936 68281 99935 44162 99930 89850 99929 72379 99923 96604 99921 3518 99919 19343 99915 77206 99911 43342 99906 98843 99905 81671 9...

result:

ok correct

Test #83:

score: 0
Accepted
time: 142ms
memory: 23540kb

input:

99999 400000
37837 21233
20293 37837
14486 20293
51392 14486
69837 51392
76731 69837
92598 76731
65622 92598
101 65622
61329 101
66377 61329
42365 66377
76059 42365
824 76059
90424 824
91057 90424
59145 91057
75763 59145
1246 75763
4173 1246
70545 4173
12021 70545
15636 12021
31267 15636
6881 31267
...

output:

99998 74028 99994 64429 99983 3673 99978 5746 99972 49143 99946 50062 99941 37024 99935 3952 99932 24160 99925 46513 99923 71574 99916 22615 99914 97416 99912 47857 99911 74221 99906 73489 99899 54461 99897 73312 99894 35064 99887 61422 99880 73367 99870 99603 99859 95728 99853 45656 99849 52213 998...

result:

ok correct

Subtask #11:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Subtask #12:

score: 16
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Subtask #13:

score: 21
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #8:

100%
Accepted

Subtask #14:

score: 19
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #9:

100%
Accepted

Subtask #15:

score: 34
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Dependency #8:

100%
Accepted

Dependency #9:

100%
Accepted

Dependency #10:

100%
Accepted

Dependency #11:

100%
Accepted

Dependency #12:

100%
Accepted

Dependency #13:

100%
Accepted

Dependency #14:

100%
Accepted

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-11-29 11:57:04 | OpenSource Project