QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111322#4996. Icy ItineraryPetroTarnavskyi#WA 432ms74616kbC++172.3kb2023-06-06 18:42:012023-06-06 18:42:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-06 18:42:03]
  • 评测
  • 测评结果:WA
  • 用时:432ms
  • 内存:74616kb
  • [2023-06-06 18:42:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 300'447;
VI g[N];
VI g2[N];
int s[N];
bool used[N];
set<int> all;
set<PII> cmp;
int lef;

int dfs1(int v)
{
	used[v] = 1;
	s[v] = 1;
	for (auto to : g[v])
	{
		if (!used[to])
		{
			s[v] += dfs1(to);
			g2[v].PB(to);
		}
	}
	return s[v];
}

int dfs2(int v)
{
	all.erase(v);
	auto it = all.begin();
	s[v] = 1;
	FOR (i, 0, SZ(g[v]))
	{
		if (it == all.end()) return s[v];
		auto to = g[v][i];
		if (to < *it) continue;
		if (to == *it)
		{
			it++;
			continue;
		}
		to = *it;
		s[v] += dfs2(to);
		g2[v].PB(to);
		it = all.lower_bound(to);
	}
	while(it != all.end()){
		int	to = *it;
		//cerr << v << ": " << to << endl;
		
		s[v] += dfs2(to);
		g2[v].PB(to);
		it = all.lower_bound(to);
	}

	return s[v];
}

void restore(int v)
{
	cout << v + 1 << ' ';
	cmp.erase({s[v], v});
	int tot = -1;
	if(!cmp.empty())
		tot = cmp.rbegin()->second;
	for (auto to : g2[v])
	{
		cmp.insert({s[to], to});
	}	
	if(tot != -1)
		restore(tot);
}

void dfs3(int v)
{
	cout << v + 1 << ' ';
	lef--;
	cmp.erase({s[v], v});
	int mxOld = (cmp.empty() ? -1 : cmp.rbegin()->second);
	
	
	for (auto to : g2[v])
	{
		cmp.insert({s[to], to});
	}	
	
	if(mxOld != -1 && (cmp.rbegin()->first * 2 < lef + 1 || s[mxOld] == cmp.rbegin()->first)){
		restore(mxOld);
		cout << endl;
		exit(0);
	}
	
	 
	sort(ALL(g2[v]), [&](int a, int b)
	{
		return s[a] > s[b];
	});
	if(!g2[v].empty())
		dfs3(g2[v][0]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	lef = n;
	
	FOR (i, 0, m)
	{
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	int sz = dfs1(0);
	if (sz != n)
	{
		FOR (i, 0, n) 
		{
			s[i] = 0;
			g2[i].clear();
			sort(ALL(g[i]));
			used[i] = false;
			all.insert(i);
		}
		dfs2(0);
		/*FOR(i, 0, n){
			for(int to : g2[i])
				cout << to << " ";
			cout << endl;
		}*/
	}
	dfs3(0);
	cout << endl;
	assert(lef == 0);
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 12ms
memory: 17508kb

input:

4 4
1 2
1 3
1 4
3 4

output:

1 3 2 4 

result:

ok qwq

Test #2:

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

input:

5 0

output:

1 2 3 4 5 

result:

ok qwq

Test #3:

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

input:

10 10
7 8
7 5
5 2
6 1
10 7
4 6
5 8
3 2
10 5
1 10

output:

1 2 4 3 5 6 7 9 8 10 

result:

ok qwq

Test #4:

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

input:

2 1
1 2

output:

1 2 

result:

ok qwq

Test #5:

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

input:

2 0

output:

1 2 

result:

ok qwq

Test #6:

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

input:

3 1
1 3

output:

1 2 3 

result:

ok qwq

Test #7:

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

input:

10 40
10 9
4 5
2 7
3 4
4 7
4 9
7 3
5 10
5 9
8 1
1 10
6 7
6 9
9 8
10 7
7 8
8 3
10 3
2 1
1 5
6 1
5 7
2 5
3 9
2 8
1 9
4 1
1 7
4 10
2 10
3 1
4 6
9 7
3 6
2 3
8 4
6 8
3 5
4 2
2 6

output:

1 8 9 10 5 4 3 7 2 6 

result:

ok qwq

Test #8:

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

input:

10 45
7 2
6 3
7 10
5 1
1 9
6 8
10 1
2 10
10 8
10 5
6 2
4 3
6 7
10 3
3 2
1 8
10 9
2 5
9 2
4 1
8 3
8 2
5 7
4 8
9 4
1 7
7 3
6 10
4 2
6 4
10 4
3 1
8 5
4 7
1 6
9 5
3 9
6 5
5 4
9 7
2 1
8 9
3 5
6 9
7 8

output:

1 5 10 7 2 6 3 4 8 9 

result:

ok qwq

Test #9:

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

input:

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

output:

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

result:

ok qwq

Test #10:

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

input:

15 1
13 6

output:

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

result:

ok qwq

Test #11:

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

input:

150 150
110 99
80 122
55 67
24 47
73 68
150 13
94 140
146 59
136 28
94 134
131 2
26 105
65 79
57 37
116 102
84 16
110 78
72 5
34 8
8 43
83 57
49 146
43 112
54 139
95 13
11 95
75 29
29 30
52 14
118 56
4 51
18 146
31 113
56 69
44 14
63 123
44 66
101 122
52 10
16 118
71 93
22 113
28 88
5 108
16 48
84 1...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 15 17 18 19 20 21 22 23 24 25 26 27 28 29 31 30 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 71 70 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok qwq

Test #12:

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

input:

1500 1500
370 639
1046 375
1191 907
782 923
1369 196
998 194
640 331
309 631
1053 1076
887 1112
650 1437
2 1133
847 302
647 81
22 691
772 14
1112 62
266 1399
865 980
1302 1146
1007 575
1448 261
1489 1189
1134 1009
7 1175
1369 942
709 365
675 514
1021 1250
1415 2
976 746
564 388
431 326
43 147
385 81...

output:

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

result:

ok qwq

Test #13:

score: 0
Accepted
time: 17ms
memory: 20404kb

input:

15000 15000
11602 9990
5492 14226
2633 14599
7956 12544
1258 1198
13788 3283
171 3770
8226 10782
915 6735
7186 14219
12806 1549
8783 5596
3692 9668
370 4654
13811 4032
835 12990
14273 14020
8902 7798
7405 4524
7476 1864
7786 14984
4367 13552
2927 2463
1929 3198
97 5800
14012 5674
6283 827
13860 1139...

output:

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

result:

ok qwq

Test #14:

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

input:

300000 0

output:

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

result:

ok qwq

Test #15:

score: 0
Accepted
time: 148ms
memory: 61172kb

input:

300000 1
80856 110687

output:

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

result:

ok qwq

Test #16:

score: 0
Accepted
time: 135ms
memory: 61200kb

input:

300000 100
254473 70041
278954 218026
54339 23948
90766 35432
145294 42945
10824 168971
162204 196321
137959 274421
274330 8901
113606 229638
136217 161945
232685 214848
91296 146678
8764 206628
297190 163150
140047 161791
188167 261504
261443 160497
262029 233857
112139 37654
43010 192683
3697 1727...

output:

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

result:

ok qwq

Test #17:

score: 0
Accepted
time: 207ms
memory: 65796kb

input:

300000 100000
279619 105099
95580 46691
139476 105331
67098 144910
105689 84242
198438 147050
274697 179922
229381 179041
210820 243557
162433 137909
14644 17464
295783 151723
180167 63360
17314 119555
201506 121519
129982 11913
3312 283798
197026 175391
86210 36036
177182 150502
37900 95301
261630 ...

output:

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

result:

ok qwq

Test #18:

score: 0
Accepted
time: 432ms
memory: 74616kb

input:

300000 300000
297121 280398
49505 181149
186167 88552
250816 195719
113345 180891
103968 274040
148345 167433
283785 32444
281156 62491
76167 222701
181130 69399
291957 220950
21996 17907
98113 270806
247895 36687
122761 248769
235623 41248
274601 174896
296046 235115
57460 64170
286130 15089
91951 ...

output:

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

result:

ok qwq

Test #19:

score: 0
Accepted
time: 44ms
memory: 21860kb

input:

1000 300000
794 378
253 365
792 287
235 482
50 807
795 174
786 980
763 645
615 440
364 542
209 856
925 709
965 709
755 592
242 870
960 978
253 404
164 439
931 998
443 318
663 958
560 445
970 245
192 631
321 621
120 472
402 520
939 454
436 893
840 577
112 961
509 9
815 190
357 128
52 433
554 967
384 ...

output:

1 456 330 310 830 147 212 915 407 997 811 710 624 955 412 160 481 67 649 967 554 788 883 84 749 880 695 148 61 295 483 572 389 560 445 765 198 800 332 714 109 950 862 204 684 794 378 591 116 886 802 53 566 37 751 163 528 727 505 194 747 23 58 159 369 864 350 31 610 299 443 318 286 115 438 564 529 72...

result:

ok qwq

Test #20:

score: 0
Accepted
time: 50ms
memory: 20852kb

input:

1500 300000
1189 1031
85 1047
1096 1290
1497 193
885 27
603 979
1438 1441
507 1256
1432 803
332 750
536 157
333 1248
1009 943
857 422
849 796
1399 814
911 481
836 36
1360 1175
592 737
277 672
551 331
849 1049
725 343
1312 112
889 544
1154 691
1387 1326
91 481
432 689
1051 248
1069 1499
499 194
748 1...

output:

1 793 1295 944 167 928 1158 982 881 472 1211 691 1154 677 850 592 737 386 578 203 313 183 26 516 857 422 155 717 257 532 1084 924 841 754 1273 669 100 912 38 263 743 87 491 651 452 817 700 1101 455 457 540 186 1127 70 828 822 1017 1272 1339 530 1271 607 1246 1492 746 318 548 412 97 800 875 1411 959 ...

result:

ok qwq

Test #21:

score: 0
Accepted
time: 72ms
memory: 22440kb

input:

10000 300000
1236 4556
6003 6937
2217 6717
1150 1520
835 87
6994 6123
4263 8371
6772 4802
7302 3130
6157 4469
9918 3820
1997 5129
9662 7860
5882 9655
4931 8546
4776 1017
3925 6960
8114 6760
7793 3511
2958 3481
7244 3603
8609 4155
1832 2597
1639 6861
6563 8641
7870 3706
3772 4396
7696 6907
8722 1019
...

output:

1 5593 3273 1886 6595 1063 1643 9534 5164 5759 5738 5249 9753 3320 7441 1442 8646 5927 1676 4156 4047 5965 8908 1715 1984 5375 7084 9304 9271 4746 1217 8978 4725 3474 8265 4048 6698 6081 6575 2548 9043 1414 2416 9741 790 283 2950 8122 4382 7528 6486 6901 4625 9432 1812 1874 5085 6732 1766 15 5471 13...

result:

ok qwq

Test #22:

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

input:

10 40
1 5
2 5
3 5
4 5
6 5
7 5
8 5
9 5
10 5
1 2
3 2
4 2
6 2
7 2
8 2
9 2
10 2
1 4
3 4
6 4
7 4
8 4
9 4
10 4
1 10
3 10
6 10
7 10
8 10
9 10
1 3
6 3
7 3
8 3
9 3
1 8
6 8
7 8
9 8
1 9

output:

1 5 2 3 4 6 10 7 8 9 

result:

ok qwq

Test #23:

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

input:

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

output:

1 7 2 72 64 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 71 70 69 68 67 66 65 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 

result:

ok qwq

Test #24:

score: 0
Accepted
time: 29ms
memory: 20500kb

input:

1000 300000
1 965
2 965
3 965
4 965
5 965
6 965
7 965
8 965
9 965
10 965
11 965
12 965
13 965
14 965
15 965
16 965
17 965
18 965
19 965
20 965
21 965
22 965
23 965
24 965
25 965
26 965
27 965
28 965
29 965
30 965
31 965
32 965
33 965
34 965
35 965
36 965
37 965
38 965
39 965
40 965
41 965
42 965
43 ...

output:

1 965 2 780 3 24 4 538 5 255 6 305 7 836 8 839 9 162 10 417 11 343 12 508 13 168 14 100 15 547 16 834 17 273 18 990 19 54 20 999 21 89 22 86 23 745 25 487 26 661 27 63 28 344 29 297 30 932 31 552 32 435 33 212 34 113 35 830 36 629 37 148 38 789 39 705 40 137 41 829 42 152 43 918 44 940 45 426 46 701...

result:

ok qwq

Test #25:

score: 0
Accepted
time: 31ms
memory: 20800kb

input:

3000 300000
1 395
2 395
3 395
4 395
5 395
6 395
7 395
8 395
9 395
10 395
11 395
12 395
13 395
14 395
15 395
16 395
17 395
18 395
19 395
20 395
21 395
22 395
23 395
24 395
25 395
26 395
27 395
28 395
29 395
30 395
31 395
32 395
33 395
34 395
35 395
36 395
37 395
38 395
39 395
40 395
41 395
42 395
43 ...

output:

1 395 2 40 3 2831 4 255 5 1861 6 1085 7 2917 8 1134 9 364 10 1450 11 2185 12 1977 13 1827 14 2389 15 316 16 1319 17 1984 18 2167 19 277 20 2961 21 2671 22 834 23 957 24 317 25 1069 26 1912 27 2903 28 1301 29 2345 30 1037 31 1813 32 80 33 1416 34 2013 35 66 36 2446 37 2602 38 2392 39 206 41 319 42 18...

result:

ok qwq

Test #26:

score: 0
Accepted
time: 35ms
memory: 20672kb

input:

10000 300000
1 9020
2 9020
3 9020
4 9020
5 9020
6 9020
7 9020
8 9020
9 9020
10 9020
11 9020
12 9020
13 9020
14 9020
15 9020
16 9020
17 9020
18 9020
19 9020
20 9020
21 9020
22 9020
23 9020
24 9020
25 9020
26 9020
27 9020
28 9020
29 9020
30 9020
31 9020
32 9020
33 9020
34 9020
35 9020
36 9020
37 9020
...

output:

1 9020 2 5337 3 6566 4 4623 5 4607 6 5399 7 7531 8 6820 9 6572 10 8835 11 8934 12 9652 13 9798 14 707 15 5837 16 2349 17 2560 18 9659 19 9532 20 3419 21 4505 22 1488 23 5394 24 3859 25 4573 26 4595 27 2428 28 2145 29 6149 30 1131 31 10000 3097 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9...

result:

ok qwq

Test #27:

score: 0
Accepted
time: 66ms
memory: 22568kb

input:

40000 300000
1 8681
2 8681
3 8681
4 8681
5 8681
6 8681
7 8681
8 8681
9 8681
10 8681
11 8681
12 8681
13 8681
14 8681
15 8681
16 8681
17 8681
18 8681
19 8681
20 8681
21 8681
22 8681
23 8681
24 8681
25 8681
26 8681
27 8681
28 8681
29 8681
30 8681
31 8681
32 8681
33 8681
34 8681
35 8681
36 8681
37 8681
...

output:

1 8681 2 15643 3 39633 4 31561 5 1513 6 23833 7 5018 8 18782 40000 39999 39998 39997 39996 39995 39994 39993 39992 39991 39990 39989 39988 39987 39986 39985 39984 39983 39982 39981 39980 39979 39978 39977 39976 39975 39974 39973 39972 39971 39970 39969 39968 39967 39966 39965 39964 39963 39962 39961...

result:

ok qwq

Test #28:

score: 0
Accepted
time: 84ms
memory: 27140kb

input:

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

output:

1 97406 2 15583 3 10856 4 100000 39038 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 999...

result:

ok qwq

Test #29:

score: 0
Accepted
time: 176ms
memory: 44488kb

input:

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

output:

1 193103 199999 300000 299999 299998 299997 299996 299995 299994 299993 299992 299991 299990 299989 299988 299987 299986 299985 299984 299983 299982 299981 299980 299979 299978 299977 299976 299975 299974 299973 299972 299971 299970 299969 299968 299967 299966 299965 299964 299963 299962 299961 2999...

result:

ok qwq

Test #30:

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

input:

1000 249500
1 702
1 559
1 154
1 284
1 707
1 397
1 281
1 105
1 856
1 712
1 864
1 638
1 640
1 984
1 134
1 819
1 36
1 820
1 146
1 779
1 516
1 420
1 721
1 932
1 426
1 922
1 790
1 167
1 365
1 667
1 690
1 357
1 543
1 778
1 473
1 9
1 239
1 746
1 983
1 141
1 349
1 852
1 826
1 553
1 929
1 628
1 500
1 352
1 6...

output:

1 4 2 5 3 8 6 11 7 13 9 14 10 15 12 16 17 19 18 23 20 24 21 25 22 26 28 27 30 29 32 31 35 33 36 34 37 38 39 40 41 43 42 45 44 46 47 48 50 49 51 54 52 55 53 58 56 59 57 61 60 69 62 70 63 72 64 73 65 74 66 75 67 77 68 78 71 79 76 81 80 88 82 89 83 92 84 95 85 96 86 97 87 102 90 103 91 107 93 109 94 11...

result:

ok qwq

Test #31:

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

input:

750 245875
1 596
1 476
1 375
1 129
1 650
1 604
1 579
1 302
1 574
1 322
1 351
1 206
1 107
1 535
1 597
1 135
1 516
1 330
1 515
1 151
1 357
1 146
1 4
1 150
1 85
1 15
1 655
1 227
1 549
1 311
1 560
1 705
1 273
1 249
1 307
1 191
1 398
1 691
1 621
1 257
1 268
1 729
1 593
1 61
1 139
1 630
1 172
1 740
1 306
...

output:

1 2 4 3 15 5 61 6 85 7 107 8 129 9 135 10 139 11 146 12 150 13 151 14 172 16 191 17 206 18 227 19 249 20 257 21 268 22 273 23 302 24 306 25 307 26 311 27 322 28 330 29 351 30 357 31 375 32 398 33 476 34 515 35 516 36 535 37 549 38 560 39 574 40 579 41 593 42 596 43 597 44 604 45 621 46 630 47 650 48...

result:

ok qwq

Test #32:

score: 0
Accepted
time: 44ms
memory: 20384kb

input:

750 245875
1 368
1 278
1 71
1 353
1 405
1 149
1 616
1 153
1 622
1 655
1 105
1 682
1 140
1 668
1 352
1 210
1 257
1 677
1 749
1 612
1 234
1 35
1 400
1 604
1 193
1 505
1 230
1 586
1 358
1 737
1 428
1 346
1 279
1 395
1 584
1 691
1 73
1 435
1 639
1 205
1 320
1 496
1 384
1 295
1 522
1 672
1 309
1 250
1 43...

output:

1 26 2 45 3 64 4 72 5 86 6 93 7 94 8 101 9 161 10 177 11 185 12 196 13 214 14 218 15 241 16 243 17 287 18 290 19 332 20 339 21 367 22 372 23 379 24 382 25 389 27 396 28 403 29 415 30 427 31 474 32 475 33 477 34 501 35 508 36 519 37 538 38 571 39 576 40 591 41 627 42 629 43 656 44 661 46 662 47 685 4...

result:

ok qwq

Test #33:

score: 0
Accepted
time: 18ms
memory: 18676kb

input:

750 101324
1 411
1 270
1 170
1 697
1 76
1 64
1 744
1 353
1 109
1 115
1 133
1 560
1 453
1 690
1 297
1 733
1 523
1 479
1 62
1 32
1 80
1 578
1 261
1 682
1 506
1 303
1 646
1 229
1 750
1 421
1 322
1 168
1 543
1 568
1 456
1 138
1 57
1 380
1 534
1 131
1 452
1 614
1 174
1 207
1 617
1 123
1 562
1 69
1 567
1 ...

output:

1 3 2 4 5 6 7 8 9 10 11 12 13 18 14 20 15 23 16 29 17 31 19 32 21 37 22 39 24 43 25 44 26 48 27 49 28 57 30 60 33 61 34 62 35 63 36 64 38 65 40 66 41 69 42 71 45 72 46 76 47 77 50 80 51 88 52 89 53 93 54 95 55 96 56 97 58 102 59 104 67 105 68 106 70 109 73 113 74 115 75 117 78 122 79 123 81 125 82 1...

result:

ok qwq

Test #34:

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

input:

750 45299
1 415
1 743
1 571
1 531
1 419
1 378
1 188
1 454
1 117
1 344
1 362
1 180
1 461
1 228
1 693
1 115
1 275
1 250
1 501
1 618
1 322
1 217
1 42
1 398
1 129
1 88
1 414
1 740
1 90
1 528
1 437
1 124
1 733
1 241
1 487
1 72
1 295
1 366
1 748
1 143
1 55
1 113
1 534
1 479
1 555
1 712
1 349
1 586
1 212
1...

output:

1 2 3 4 5 6 7 8 10 9 12 11 15 13 16 14 17 18 21 19 22 20 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 50 49 51 52 53 56 54 60 55 61 57 62 58 63 59 64 65 66 67 68 69 70 71 75 72 76 73 77 74 78 79 80 81 82 83 86 84 87 85 92 88 93 89 95 90 97 91 98 94 99 96 102 100 103 ...

result:

ok qwq

Test #35:

score: 0
Accepted
time: 45ms
memory: 20140kb

input:

750 258869
1 124
1 233
1 740
1 493
1 145
1 749
1 142
1 224
1 308
1 572
1 33
1 660
1 246
1 377
1 690
1 105
1 741
1 692
1 497
1 334
1 481
1 450
1 366
1 307
1 739
1 165
1 730
1 430
1 332
52 349
52 424
52 212
52 555
52 531
52 426
52 379
52 637
52 635
52 434
52 40
52 404
52 261
52 190
52 557
52 225
52 52...

output:

1 2 33 3 105 4 124 5 142 6 145 7 165 8 224 9 233 10 246 11 307 12 308 13 332 14 334 15 366 16 377 17 430 18 450 19 481 20 493 21 497 22 572 23 660 24 690 25 692 26 730 27 739 28 740 29 741 30 749 515 750 748 747 746 745 744 743 742 738 737 736 735 734 733 732 731 729 728 727 726 725 724 723 722 721 ...

result:

ok qwq

Test #36:

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

input:

750 1154
1 433
1 99
1 563
1 370
1 149
1 218
1 477
1 170
1 98
1 299
1 586
1 574
1 51
1 667
1 539
1 659
1 615
1 730
1 12
1 694
1 695
1 662
1 166
1 253
1 84
1 420
1 533
1 231
1 410
433 99
433 563
433 370
433 149
433 218
433 477
433 170
433 98
433 299
433 586
433 574
433 51
433 667
433 539
433 659
433 6...

output:

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 100 99 101 102 ...

result:

ok qwq

Test #37:

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

input:

750 1924
1 211
1 576
1 697
1 175
1 675
1 641
1 301
1 227
1 311
1 669
1 637
1 673
1 245
1 548
1 74
1 740
1 134
1 561
1 90
1 185
1 511
1 57
1 478
1 423
1 310
1 741
1 550
1 7
1 712
1 725
1 293
1 361
1 593
1 558
1 414
1 356
1 94
1 120
1 700
1 60
1 434
1 226
1 647
1 453
1 328
1 221
1 28
1 352
1 11
1 654
...

output:

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

result:

ok qwq

Test #38:

score: 0
Accepted
time: 46ms
memory: 20524kb

input:

750 244699
1 235
1 228
1 716
1 27
1 55
1 706
1 313
1 247
1 131
1 120
1 446
1 25
1 615
1 351
1 712
1 606
1 406
1 324
1 356
1 182
1 622
1 230
1 497
1 511
1 163
1 137
1 630
1 434
1 273
1 350
1 297
1 674
1 605
1 109
1 707
1 101
1 78
1 691
1 133
1 705
1 354
1 115
1 735
1 384
1 211
1 364
1 386
1 663
1 54
...

output:

1 7 2 21 3 28 4 44 5 66 6 74 8 87 9 89 10 95 11 103 12 105 13 110 14 130 15 145 16 165 17 176 18 178 19 180 20 237 22 242 23 254 24 257 25 258 26 325 27 332 29 340 30 360 31 370 32 396 33 415 34 441 35 447 36 482 37 506 38 507 39 513 40 516 41 535 42 540 43 549 45 555 46 591 47 593 48 631 49 632 50 ...

result:

ok qwq

Test #39:

score: 0
Accepted
time: 51ms
memory: 20756kb

input:

1500 281624
1 1109
1 1191
1 775
1 218
1 867
1 1135
1 1484
1 72
1 523
1 502
1 1296
1 187
1 1241
1 1178
1 1099
1 305
1 962
1 431
1 813
1 368
1 755
1 722
1 404
1 1092
1 1263
1 999
1 704
1 1096
1 1234
1 645
1 504
1 246
1 365
1 624
1 838
1 1061
1 1458
1 430
1 738
1 1349
1 302
1 691
1 1098
1 1437
1 250
1 ...

output:

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

result:

ok qwq

Test #40:

score: 0
Accepted
time: 62ms
memory: 20836kb

input:

1500 281624
1 359
1 429
1 391
1 904
1 152
1 321
1 1361
1 435
1 1043
1 1059
1 669
1 1437
1 548
1 186
1 278
1 416
1 618
1 1472
1 634
1 806
1 503
1 713
1 1197
1 252
1 960
1 1341
1 366
1 302
1 623
1 226
1 52
1 1034
1 448
1 738
1 430
1 408
1 1366
1 874
1 727
1 18
1 240
1 1294
1 301
1 141
1 1046
1 369
1 9...

output:

1 7 2 10 3 12 4 15 5 19 6 20 8 22 9 23 11 24 13 25 14 26 16 30 17 31 18 37 21 39 27 40 28 41 29 46 32 48 33 53 34 56 35 57 36 60 38 63 42 64 43 68 44 74 45 76 47 77 49 78 50 80 51 83 52 85 54 87 55 88 58 89 59 92 61 94 62 96 65 97 66 99 67 101 69 102 70 103 71 105 72 109 73 110 75 111 79 112 81 113 ...

result:

ok qwq

Test #41:

score: 0
Accepted
time: 28ms
memory: 19588kb

input:

1000 250000
1 576
1 827
1 255
1 901
1 254
1 217
1 553
1 531
1 436
1 209
1 339
1 765
1 21
1 610
1 235
1 613
1 495
1 918
1 299
1 512
1 628
1 68
1 4
1 421
1 422
1 858
1 587
1 458
1 154
1 487
1 205
1 687
1 227
1 279
1 394
1 608
1 802
1 656
1 548
1 286
1 752
1 544
1 821
1 328
1 751
1 175
1 801
1 871
1 99...

output:

1 576 866 827 812 255 431 901 521 254 415 217 612 553 56 531 482 436 523 209 662 339 188 765 963 21 759 610 367 235 667 613 189 495 237 918 904 299 165 512 931 628 990 68 491 4 595 421 563 422 37 858 368 587 684 458 493 154 232 487 893 205 773 687 445 227 855 279 720 394 292 608 867 802 345 656 132 ...

result:

ok qwq

Test #42:

score: 0
Accepted
time: 28ms
memory: 19656kb

input:

750 235576
1 584
1 479
1 457
1 589
1 456
1 195
1 284
1 120
1 220
1 340
1 566
1 134
1 661
1 666
1 742
1 702
1 563
1 246
1 370
1 415
1 388
1 159
1 532
1 209
1 121
1 157
1 573
1 272
1 77
1 454
1 487
1 471
1 545
1 600
1 256
1 262
1 612
1 58
1 131
1 607
1 403
1 124
1 691
1 571
1 534
1 740
1 43
1 482
1 19...

output:

1 584 409 479 189 457 562 589 706 456 234 195 362 284 466 120 215 220 643 340 60 566 413 134 555 661 288 666 332 742 267 702 20 563 384 246 510 370 536 415 695 388 324 159 239 532 380 209 143 121 173 157 451 573 503 272 425 77 162 454 506 487 707 471 374 545 386 600 183 256 659 262 164 612 355 58 59...

result:

ok qwq

Test #43:

score: 0
Accepted
time: 63ms
memory: 19788kb

input:

1000 250000
1 54
1 332
1 325
1 717
1 164
1 931
1 373
1 578
1 788
1 290
1 900
1 610
1 646
1 531
1 188
1 600
1 448
1 625
1 728
1 320
1 461
1 204
1 558
1 665
1 629
1 869
1 100
1 340
1 268
1 715
1 338
1 608
1 353
1 777
1 264
1 771
1 835
1 169
1 276
1 601
1 895
1 661
1 507
1 611
1 568
1 475
1 863
1 510
1...

output:

1 54 889 332 549 325 10 717 483 164 910 931 890 373 636 578 474 788 172 290 413 900 183 610 659 646 476 531 283 188 517 600 44 448 934 625 674 728 702 320 72 461 864 204 62 558 397 665 828 629 260 869 700 100 267 340 542 268 65 715 667 338 748 608 699 353 844 777 451 264 317 771 916 835 909 169 738 ...

result:

ok qwq

Test #44:

score: 0
Accepted
time: 25ms
memory: 20196kb

input:

700 226506
1 663
1 483
1 532
1 537
1 492
1 641
1 648
1 208
1 472
1 266
1 662
1 91
1 379
1 463
1 297
1 61
1 23
1 530
1 12
1 411
1 322
1 17
1 654
1 451
1 329
1 351
1 162
1 283
1 501
1 643
1 403
1 627
1 386
1 251
1 19
1 92
1 350
1 69
1 55
1 65
1 73
1 528
1 432
1 371
1 597
1 605
1 202
1 498
1 177
1 222
...

output:

1 283 501 643 403 627 386 251 19 92 350 69 55 65 73 528 432 371 597 605 202 498 177 222 617 331 96 645 99 48 640 320 565 68 154 16 457 243 637 2 190 175 487 652 308 223 365 569 84 561 258 121 402 668 671 213 229 241 490 397 677 79 120 598 236 45 143 373 644 270 620 305 358 635 4 302 342 433 382 215 ...

result:

ok qwq

Test #45:

score: -100
Wrong Answer
time: 42ms
memory: 19824kb

input:

1000 249494
933 199
933 48
933 238
933 122
933 17
933 573
933 592
933 505
933 784
933 165
933 840
933 809
933 676
933 565
933 353
933 819
933 425
933 423
933 185
933 733
933 580
933 870
933 257
933 735
933 629
933 114
933 200
933 181
933 1000
933 951
933 538
933 658
933 318
933 171
933 841
933 258
9...

output:

1 2 3 4 5 6 7 8 12 15 17 18 19 20 22 25 26 27 32 33 34 41 45 47 48 49 50 51 52 53 54 56 58 63 64 67 68 69 70 71 72 77 78 82 83 84 86 88 89 90 91 93 94 96 97 98 99 100 101 102 103 104 106 110 112 114 117 118 119 120 121 122 124 126 129 131 137 141 144 147 148 149 151 152 158 163 165 167 168 169 170 1...

result:

wrong answer Changed color too many times (3)