QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#154208#6414. Classical Maximization ProblemPhantomThreshold#TL 516ms7376kbC++201.6kb2023-08-31 15:03:022023-08-31 15:03:04

Judging History

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

  • [2023-08-31 15:03:04]
  • 评测
  • 测评结果:TL
  • 用时:516ms
  • 内存:7376kb
  • [2023-08-31 15:03:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		n*=2;
		vector<int> x(n+5),y(n+5);
		map<int,map<int,int>> sx,sy;
		for(int i=1;i<=n;i++)
		{
			cin>>x[i]>>y[i];
			sx[x[i]][y[i]]=i;
			sy[y[i]][x[i]]=i;
		}
		vector<int> vis(n+5);
		vector<pair<int,int>> ans;
		function<int(int,int)> dfs=[&](int u,int ty)//0:x,1:y
		{
			vis[u]=1;
			vector<int> remx,remy;
			for(auto [y0,v]:sx[x[u]])
			{
				if(not vis[v])
				{
					int r=dfs(v,0);
					if(r)remx.push_back(r);
				}
			}
			for(auto [x0,v]:sy[y[u]])
			{
				if(not vis[v])
				{
					int r=dfs(v,1);
					if(r)remy.push_back(r);
				}
			}
			int sz=remx.size();
			for(int i=0;i+1<sz;i+=2)
			{
				ans.emplace_back(remx[i],remx[i+1]);
			}
			int rx=0;
			if(sz%2==1)rx=remx[sz-1];
			sz=remy.size();
			for(int i=0;i+1<sz;i+=2)
			{
				ans.emplace_back(remy[i],remy[i+1]);
			}
			int ry=0;
			if(sz%2==1)ry=remy[sz-1];
			if(not rx and not ry)
			{
				return u;
			}
			else if(rx and ry)
			{
				if(ty)
				{
					ans.emplace_back(u,rx);
					return ry;
				}
				else
				{
					ans.emplace_back(u,ry);
					return rx;
				}
			}
			else
			{
				ans.emplace_back(u,rx|ry);
				return 0;
			}
		};
		vector<int> rem;
		for(int i=1;i<=n;i++)
		{
			if(not vis[i])
			{
				int r=dfs(i,0);
				if(r)rem.push_back(r);
			}
		}
		cout<<ans.size()<<endl;
		for(unsigned i=0;i<rem.size();i+=2)
			ans.emplace_back(rem[i],rem[i+1]);
		for(auto [u,v]:ans)
		{
			cout<<u<<' '<<v<<"\n";
		}
	}
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3572kb

input:

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

output:

2
4 3
1 2
2
3 4
1 2
0
1 2
3 4

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 123ms
memory: 3556kb

input:

10000
2
-107276936 -310501829
419434212 585811870
-65754386 -491212232
381152038 897148193
3
-474045168 493506332
299114415 540203303
165808153 983551
-506936261 -694189769
766718170 -725540031
975267148 -593051087
1
-818952276 -762387923
584023914 -612401389
6
-77701228 -266484128
659434465 6322062...

output:

0
1 2
3 4
0
1 2
3 4
5 6
0
1 2
0
1 2
3 4
5 6
7 8
9 10
11 12
0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
0
1 2
0
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
0
1 2
3 4...

result:

ok ok (10000 test cases)

Test #3:

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

input:

10000
1
999855386 999580905
999342928 999615227
21
999601032 999015398
999155628 999176944
999309856 999524434
999121011 999509537
999323572 999685730
999272272 999769606
999450559 999390758
999632027 999178534
999024993 999463838
999784856 999374197
999980525 999366771
999241260 999516879
999599548...

output:

0
1 2
0
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
0
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
0
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
0
1 2
3 4
5 6
7...

result:

ok ok (10000 test cases)

Test #4:

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

input:

10000
5
999984799 999981445
999958394 999984217
999994978 999981258
999955539 999938710
999936554 999963561
999907222 999907508
999938166 999941959
999910567 999986887
999901446 999961092
999994730 999963038
5
999916115 999962400
999948250 999940355
999954204 999920844
999928148 999990369
999978118 ...

output:

0
1 2
3 4
5 6
7 8
9 10
0
1 2
3 4
5 6
7 8
9 10
0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
0
1 2
3 4
5 6
7 8
0
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
0
1 2
3 4
5 6
7 8
9 10
0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
0
1 2
3 4
5 6
7 8
9 10
1...

result:

ok ok (10000 test cases)

Test #5:

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

input:

10000
1
999990146 999993828
999995909 999996353
56
999999851 999991179
999997250 999997987
999990590 999997316
999997350 999996856
999997034 999996236
999999396 999996897
999991180 999993309
999991265 999995185
999993952 999994054
999990210 999994471
999993201 999995893
999997170 999998971
999998201...

output:

0
1 2
1
76 111
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 77
78 79
80 81
82 83
84 85
86 87
88 89
90 91
92 93
94 95
96 97
98 99
...

result:

ok ok (10000 test cases)

Test #6:

score: 0
Accepted
time: 163ms
memory: 3668kb

input:

10000
5
999999432 999999813
999999271 999999233
999999043 999999606
999999523 999999406
999999564 999999274
999999641 999999102
999999903 999999858
999999058 999999098
999999974 999999119
999999643 999999620
5
999999370 999999738
999999181 999999907
999999163 999999783
999999393 999999086
999999661 ...

output:

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

result:

ok ok (10000 test cases)

Test #7:

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

input:

10000
14
-369804569 -904204119
526374829 -824374353
-127549933 -904204119
-68608787 929413707
-68608787 -363454459
526374829 929413707
693313139 -824374353
-127549933 -726843762
526374829 -904204119
526374829 -363454459
526374829 -409731440
693313139 -726843762
693313139 929413707
-68608787 -8243743...

output:

14
12 28
27 7
13 24
11 6
9 2
10 15
16 5
23 14
18 4
8 19
3 22
26 17
21 25
1 20
20
34 9
37 11
17 23
25 2
39 14
33 19
26 35
32 15
38 4
7 22
29 30
13 27
12 24
40 21
20 5
16 36
28 6
10 31
3 8
1 18
8
15 2
13 4
9 3
16 12
14 10
11 5
6 7
1 8
1
1 2
1
1 2
34
56 66
65 62
64 35
6 36
23 22
3 59
15 39
38 16
41 52
...

result:

ok ok (10000 test cases)

Test #8:

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

input:

10000
5
-536123007 813600068
870612905 -192916365
-891077277 -192916365
-169354047 -86845158
-204880568 -86845158
-909192812 -613162163
-536123007 -613162163
602684169 -613162163
-909192812 813600068
602684169 -86845158
3
-296375355 579758813
-296375355 253508589
-296375355 -927878827
267975935 -927...

output:

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

result:

ok ok (10000 test cases)

Test #9:

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

input:

10000
13
38708650 -400244265
805800882 -207412170
-922757982 569623504
330308285 -400244265
-922757982 193222226
330308285 -701148819
-28889088 854967427
284328781 704931219
-397379302 854967427
284328781 252366771
-699696493 -701148819
953729077 -601089169
-858131099 -701148819
-397379302 193222226...

output:

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

result:

ok ok (10000 test cases)

Test #10:

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

input:

10000
2
-254673318 743896676
326182652 743896676
115024593 743896676
989112001 743896676
1
453875458 284043499
869627863 284043499
8
-68955663 625858753
-621253434 625858753
-315653340 625858753
-85160525 625858753
-592616333 625858753
114285020 625858753
618762545 625858753
524402507 625858753
1512...

output:

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

result:

ok ok (10000 test cases)

Test #11:

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

input:

10000
10
-302093372 -991014187
542702243 714369751
-370626462 -991014187
-700169063 714369751
-982732066 -991014187
-763837020 -991014187
320477527 -991014187
290144737 -991014187
18975042 -991014187
-339021181 -991014187
-525462052 -991014187
290144737 714369751
-538375359 714369751
15943074 -99101...

output:

10
7 17
19 2
12 15
9 8
18 14
3 10
20 11
4 13
6 16
1 5
10
20 10
9 8
13 4
15 17
5 12
7 6
16 19
3 11
2 18
1 14
18
12 10
2 16
31 23
30 21
15 24
18 6
8 19
32 35
5 29
3 28
27 22
33 4
20 7
26 9
25 11
17 34
36 13
1 14
35
33 12
16 19
29 48
42 44
31 27
43 7
70 41
4 5
67 25
32 26
52 20
60 40
45 59
63 11
2 68
2...

result:

ok ok (10000 test cases)

Test #12:

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

input:

10000
5
192354975 -209258445
955055576 -209258445
286707627 -209258445
-574795734 -209258445
-305243931 -209258445
-629755833 -209258445
-337515030 -209258445
980285884 -209258445
501317910 -209258445
312382135 -209258445
24
272466007 467288536
-963587196 -778274012
240097765 -778274012
-926564605 4...

output:

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

result:

ok ok (10000 test cases)

Test #13:

score: 0
Accepted
time: 201ms
memory: 3628kb

input:

10000
11
135813326 608040171
135813326 -96255413
135813326 -31734533
135813326 -423296887
135813326 999444876
135813326 946760362
135813326 -599331154
135813326 -441599790
135813326 233339336
135813326 -759375115
135813326 163868817
135813326 321091518
135813326 -402236877
135813326 625124369
135813...

output:

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

result:

ok ok (10000 test cases)

Test #14:

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

input:

10000
19
321791336 -226466052
321791336 138757626
321791336 -613429828
944682716 -446131303
321791336 -927463006
944682716 280242351
944682716 229347131
944682716 155568891
321791336 389911916
944682716 72836839
944682716 -613429828
321791336 229347131
944682716 -927463006
944682716 138757626
321791...

output:

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

result:

ok ok (10000 test cases)

Test #15:

score: 0
Accepted
time: 112ms
memory: 3708kb

input:

10000
2
414226098 -53411011
414226098 -515361565
-572270323 -515361565
-572270323 -53411011
36
660074753 623771687
-917096747 533975361
660074753 337851674
-917096747 -902052044
-917096747 846238046
660074753 197157825
660074753 533975361
660074753 626049519
-917096747 -108293477
-917096747 64055247...

output:

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

result:

ok ok (10000 test cases)

Test #16:

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

input:

10000
6
475408912 -758469962
-99052258 -758469962
-716758863 872897211
-66386054 -170278720
388817201 174925294
-776227900 -285032873
475408912 872897211
-997698204 -236300379
-716758863 -85108619
-776227900 -85108619
-716758863 -236300379
-66386054 -85108619
26
879874105 877328664
-286895493 621573...

output:

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

result:

ok ok (10000 test cases)

Test #17:

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

input:

10000
9
-980409638 -116749812
830791554 -690170434
984923479 323045898
984923479 -116749812
-197520273 323045898
-858897130 -43820432
258471629 -979749918
258471629 -690170434
-858897130 323045898
105960247 -690170434
-197520273 -841854666
-234415044 -116749812
105960247 323045898
-358435325 -202957...

output:

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

result:

ok ok (10000 test cases)

Test #18:

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

input:

1000
45
840710004 395646135
-851514725 100215150
-423513540 -649756636
464326407 -482837664
-179781718 755995077
492651722 -268519233
367302062 -111998374
494634876 842096727
973319201 399526783
-703731734 -989899930
758934136 -959677785
-682507454 58961947
394206800 272218663
752299573 489795348
89...

output:

0
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
0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15...

result:

ok ok (1000 test cases)

Test #19:

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

input:

1000
113
999827252 999728856
999923862 999631025
999319008 999580013
999333375 999174260
999509073 999545469
999194399 999278837
999715162 999728030
999881205 999764413
999917667 999953211
999651496 999869003
999693536 999169883
999545275 999786246
999969774 999735073
999892216 999697498
999954099 9...

output:

0
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 10...

result:

ok ok (1000 test cases)

Test #20:

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

input:

1000
16
999918424 999907758
999901558 999910407
999969229 999929343
999986216 999968746
999977167 999921267
999967186 999932634
999999615 999951539
999964903 999931387
999942189 999989158
999990624 999917294
999964661 999935732
999971224 999975496
999972707 999972034
999935060 999934824
999992448 99...

output:

0
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
0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
0
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 ...

result:

ok ok (1000 test cases)

Test #21:

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

input:

1000
227
999994296 999999816
999998835 999994618
999998487 999991646
999995178 999996563
999996865 999996231
999990660 999996917
999995746 999998295
999993178 999995596
999994361 999991179
999990519 999991221
999996210 999992041
999991924 999992546
999991346 999991081
999998929 999995904
999992182 9...

output:

21
3 253
9 363
10 163
22 49
43 351
90 247
100 176
109 278
112 231
124 368
128 436
135 145
142 448
148 177
172 367
180 203
235 322
263 300
297 405
315 378
340 442
1 2
4 5
6 7
8 11
12 13
14 15
16 17
18 19
20 21
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
44 45
46 47
48 50
51 52
53 54
5...

result:

ok ok (1000 test cases)

Test #22:

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

input:

1000
87
999999138 999999640
999999785 999999342
999999914 999999854
999999771 999999416
999999011 999999479
999999217 999999865
999999423 999999937
999999684 999999301
999999323 999999399
999999071 999999949
999999226 999999154
999999770 999999090
999999778 999999735
999999034 999999517
999999803 99...

output:

23
6 70
10 75
12 98
15 23
16 162
26 104
27 39
86 120
47 165
51 124
54 80
56 121
65 115
71 84
72 112
139 135
111 166
92 132
131 149
142 155
143 161
158 168
159 164
1 2
3 4
5 17
7 8
9 11
13 14
18 19
20 21
22 24
25 83
28 29
30 31
32 33
34 35
36 37
38 40
41 42
43 44
45 46
48 49
50 52
53 55
57 58
59 60
6...

result:

ok ok (1000 test cases)

Test #23:

score: 0
Accepted
time: 165ms
memory: 3992kb

input:

1000
154
825004796 802565417
-88001579 364640592
778546546 -57508543
283686672 -57508543
473326798 -826011553
152069566 -577222261
528378065 -577222261
-56296909 -700802856
-711386984 953035370
-711386984 -577222261
895677144 -359290436
840183000 364640592
528378065 -752921798
895677144 -577222261
8...

output:

154
303 17
196 290
301 254
22 300
271 130
100 236
307 269
118 38
152 188
57 83
178 139
213 151
244 119
259 11
14 235
68 169
159 93
153 140
51 252
82 304
285 12
248 44
264 150
90 220
224 50
15 206
214 107
167 149
112 79
258 3
184 98
186 223
249 23
146 75
65 52
76 28
215 158
86 87
231 246
272 99
242 3...

result:

ok ok (1000 test cases)

Test #24:

score: 0
Accepted
time: 149ms
memory: 4128kb

input:

1000
63
859289659 -203061342
831821977 -778714404
640602188 478366497
205686723 -232506600
831821977 -498015901
-494818974 35295117
612307834 -234198721
612307834 -495294231
-898414633 476295237
995217164 -232506600
831821977 934046031
-441937174 432603845
995217164 938111737
874550198 -309423823
87...

output:

63
126 113
32 51
85 112
48 3
125 76
23 114
17 105
55 66
29 26
122 75
124 110
14 104
15 116
109 106
79 70
77 46
20 64
91 89
42 41
74 119
54 6
84 97
73 58
8 7
34 101
21 92
82 27
25 16
59 28
83 121
81 19
96 13
10 36
4 94
63 103
99 90
98 123
12 117
72 107
38 49
78 31
62 118
56 22
39 71
30 86
120 52
100 ...

result:

ok ok (1000 test cases)

Test #25:

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

input:

1000
83
-242219535 -952757420
753940135 -13368420
-180286961 -530756654
586180284 -625675517
-437809383 472014390
-242857851 -924097244
-382920283 -625675517
-630990620 -349004314
-242219535 122507147
208821889 -495849186
-736086757 -489441806
-996984615 -974276781
-275306966 -25109596
967186464 -65...

output:

83
62 38
65 16
76 57
85 129
23 161
73 96
17 158
125 114
146 117
66 6
20 142
13 74
39 144
46 98
164 155
18 80
99 36
3 77
64 41
75 49
40 82
45 89
10 111
25 115
150 137
27 100
143 43
126 163
12 68
153 104
136 122
58 113
92 11
35 127
147 83
2 48
78 124
14 102
15 79
103 29
54 88
157 70
4 61
52 149
8 93
5...

result:

ok ok (1000 test cases)

Test #26:

score: 0
Accepted
time: 482ms
memory: 4144kb

input:

1000
142
-28949259 975363136
-628367037 975363136
786525293 975363136
-8339801 975363136
868048337 975363136
208733157 975363136
-724415150 975363136
213367214 975363136
-686387505 975363136
-970451747 975363136
761135553 975363136
-551594491 975363136
-925080593 975363136
-243465321 975363136
-6722...

output:

142
146 92
233 36
98 159
116 235
102 62
222 40
220 139
5 128
115 179
245 268
228 217
148 41
68 138
227 225
122 279
261 160
176 97
3 207
39 173
120 11
208 65
167 141
145 87
162 129
223 254
106 243
280 127
125 60
42 86
107 147
247 104
178 221
212 180
198 185
152 31
38 260
111 171
136 19
108 237
274 19...

result:

ok ok (1000 test cases)

Test #27:

score: 0
Accepted
time: 293ms
memory: 4136kb

input:

1000
458
102600109 754726017
-66999931 951825513
-767202008 951825513
-845069119 754726017
-448344214 754726017
174342794 754726017
176530329 754726017
553731053 754726017
-69189351 754726017
-455330522 951825513
-261324017 754726017
809818684 951825513
745593756 951825513
-130095774 754726017
-2737...

output:

458
836 805
208 146
916 259
247 143
37 905
502 155
480 314
642 393
145 248
523 48
372 244
897 556
351 399
30 859
200 903
87 119
23 241
33 42
791 328
313 403
492 262
718 618
789 95
758 100
615 326
544 728
726 868
589 760
167 222
661 660
553 398
534 896
186 424
727 796
504 804
153 306
196 570
218 576
...

result:

ok ok (1000 test cases)

Test #28:

score: 0
Accepted
time: 320ms
memory: 4232kb

input:

1000
273
638010636 -796267612
299279783 -796267612
321987052 -571635029
-388046291 -571635029
-491314021 -796267612
130988206 -571635029
32427063 -571635029
51875304 -571635029
-508530089 -796267612
269379692 -571635029
214241513 -796267612
720122947 -796267612
-678543365 -796267612
158504867 -79626...

output:

273
399 487
408 74
102 223
79 368
378 340
261 98
327 114
193 57
53 466
343 156
278 48
520 99
439 344
170 72
523 395
247 468
200 146
148 366
484 390
501 411
32 380
116 95
490 168
100 56
87 47
43 491
475 50
136 185
499 540
12 409
527 237
127 173
120 353
117 134
152 153
471 377
530 93
150 321
481 370
1...

result:

ok ok (1000 test cases)

Test #29:

score: 0
Accepted
time: 516ms
memory: 4164kb

input:

1000
75
429681826 802800421
429681826 -608943566
429681826 -787858696
429681826 507047252
429681826 485971873
429681826 -346306621
429681826 -612405192
429681826 -13671560
429681826 -816374335
429681826 513226316
429681826 892335083
429681826 -352600432
429681826 -556540475
429681826 -504699273
4296...

output:

75
59 45
92 104
123 128
124 99
11 110
48 101
113 21
80 18
68 148
122 134
138 97
89 57
96 93
126 130
39 91
30 36
10 58
23 4
5 73
112 150
63 38
86 64
15 56
137 19
98 115
61 50
52 129
125 109
37 32
20 49
75 103
60 29
143 102
31 65
77 42
43 88
8 118
107 127
82 149
33 131
25 90
135 62
136 35
70 142
146 1...

result:

ok ok (1000 test cases)

Test #30:

score: 0
Accepted
time: 288ms
memory: 4344kb

input:

1000
81
403001151 -229966312
-27290952 -941247950
-27290952 -872808715
403001151 -81762908
403001151 825473197
403001151 730971412
403001151 -886560490
-27290952 394200417
-27290952 808677817
-27290952 -961778274
-27290952 -245434545
403001151 318019109
-27290952 792029613
403001151 390473732
-27290...

output:

81
139 81
146 140
108 33
15 71
133 126
99 106
114 25
21 9
40 13
109 122
160 123
84 115
157 24
17 8
127 110
26 59
128 50
72 30
136 91
83 135
77 82
38 138
116 153
76 11
101 102
151 23
35 63
112 64
46 111
78 130
47 100
19 156
152 154
97 150
39 45
107 131
3 132
155 44
32 27
10 2
94 143
88 43
96 53
20 15...

result:

ok ok (1000 test cases)

Test #31:

score: 0
Accepted
time: 271ms
memory: 4136kb

input:

1000
257
-24981531 -524783010
-24981531 376842743
132542945 905111237
-24981531 -663183576
132542945 238995240
-24981531 -904084630
132542945 330336577
-24981531 -424310756
132542945 26224857
-24981531 573604180
132542945 -531956470
132542945 583434945
132542945 620552707
-24981531 -351085713
132542...

output:

257
337 40
220 497
155 334
199 418
310 44
280 179
3 277
439 191
238 120
358 462
395 35
435 299
512 56
469 217
366 202
252 189
480 380
205 328
319 377
118 121
226 341
314 492
434 13
321 144
213 233
12 501
504 285
100 374
362 419
75 231
417 204
382 174
131 403
244 129
495 143
87 136
260 327
236 423
42...

result:

ok ok (1000 test cases)

Test #32:

score: 0
Accepted
time: 200ms
memory: 4020kb

input:

1000
21
541263298 571344162
-338833794 258719906
814556806 571344162
749911951 -730958945
-737751671 400747496
880311857 -204125795
-555645311 -832036787
-338833794 -832036787
582588235 -915718735
-124654808 394321598
-202932677 571344162
541263298 -975674793
880311857 -730958945
-126659351 25871990...

output:

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

result:

ok ok (1000 test cases)

Test #33:

score: 0
Accepted
time: 144ms
memory: 4052kb

input:

1000
82
620344713 761205214
564192450 -149133296
855072748 -725730286
-369866361 761205214
-126903403 123500699
521658307 -238068427
564192450 -575382074
424528213 639391487
160949070 -238068427
490683515 736060786
-861287945 -430077137
92203881 -414548921
-228263452 -161807552
-739623881 619906932
...

output:

79
108 48
1 4
140 64
141 59
19 106
112 120
37 73
89 128
85 94
104 83
100 113
52 30
56 152
36 154
21 134
93 101
107 47
20 96
66 81
77 87
133 136
45 62
132 53
8 105
119 31
54 146
61 29
57 126
24 70
123 38
12 148
90 161
50 15
160 33
78 3
49 129
25 34
40 27
121 68
44 127
51 122
91 55
23 13
71 155
17 130...

result:

ok ok (1000 test cases)

Test #34:

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

input:

100
715
-716037174 449787280
-179603495 267807227
-85847745 -339745287
531498593 906672966
-65182647 -249655497
196101865 -917254384
569704541 175181937
408949063 -60772621
-471098833 -180592225
452882519 -173474204
518554869 504642822
-610596606 -43048739
-173418328 49620755
-490214353 129314297
-8...

output:

0
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 10...

result:

ok ok (100 test cases)

Test #35:

score: 0
Accepted
time: 152ms
memory: 5792kb

input:

100
1180
999939181 999607824
999877463 999501538
999725395 999197028
999578614 999669422
999691207 999388141
999798382 999350154
999515140 999686861
999804739 999722876
999059909 999779016
999988075 999795096
999394228 999790648
999357316 999130743
999834412 999146926
999533794 999419507
999164265 9...

output:

2
294 1956
485 2069
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
9...

result:

ok ok (100 test cases)

Test #36:

score: 0
Accepted
time: 158ms
memory: 6056kb

input:

100
10
999949463 999921247
999942779 999933524
999900374 999919960
999913527 999977190
999963539 999919222
999986393 999982382
999960627 999912715
999955900 999934316
999962876 999904282
999944172 999923360
999974177 999993968
999960412 999941887
999902083 999920318
999906832 999942948
999934454 999...

output:

0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
0
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...

result:

ok ok (100 test cases)

Test #37:

score: 0
Accepted
time: 160ms
memory: 6024kb

input:

100
2795
999995625 999994422
999997406 999998890
999996073 999998910
999996365 999992345
999992211 999999534
999990826 999998894
999990827 999999648
999991569 999997094
999997323 999994792
999990812 999994722
999994392 999998879
999994441 999990381
999992051 999993298
999997822 999994423
999998285 9...

output:

1710
1620 2955
1221 2278
1 1185
2121 2936
4782 887
2 3704
3 2184
4 3332
3944 3365
5 2607
3120 5539
256 1753
2471 3767
2269 3598
2883 856
8 492
4161 5579
3655 5453
1042 3895
3648 4480
2165 2576
12 2218
2449 1816
5016 1665
13 3779
4294 3453
14 188
1815 2481
1596 2889
4914 453
4200 4026
3975 1999
1788 ...

result:

ok ok (100 test cases)

Test #38:

score: 0
Accepted
time: 151ms
memory: 7128kb

input:

100
1005
999999258 999999564
999999716 999999506
999999057 999999959
999999274 999999385
999999562 999999714
999999749 999999926
999999159 999999330
999999060 999999408
999999218 999999582
999999097 999999761
999999853 999999231
999999424 999999841
999999744 999999186
999999400 999999073
999999445 9...

output:

985
1259 1932
1221 1275
1762 136
1954 774
102 1287
244 408
1354 540
772 1082
1440 1248
601 89
652 835
1141 1967
1474 1149
495 499
1290 3
1357 1532
1485 1428
780 218
119 932
1006 754
1434 497
1119 910
1976 425
1311 1630
428 331
553 1883
1324 1676
1942 490
1969 1890
146 578
1027 742
1594 1884
713 1674...

result:

ok ok (100 test cases)

Test #39:

score: 0
Accepted
time: 287ms
memory: 7040kb

input:

100
174
-958876330 -846470800
-796741809 -131152725
574295122 764287642
-958876330 -825762193
185468313 -971066749
-287559769 764287642
-904746093 -825762193
-438778854 -825762193
5267152 609322023
185468313 77515090
185468313 -131152725
-287559769 247199580
-491475497 260165013
719679418 -179087066...

output:

174
318 317
114 323
20 249
218 265
73 25
187 50
119 125
22 105
53 152
272 163
241 162
316 108
315 258
254 185
337 14
115 17
237 15
164 131
86 160
138 121
214 343
302 183
161 325
194 83
201 197
122 286
3 103
33 171
100 67
202 38
144 251
324 236
293 189
16 61
219 262
104 347
48 299
303 296
156 222
127...

result:

ok ok (100 test cases)

Test #40:

score: 0
Accepted
time: 184ms
memory: 7112kb

input:

100
454
292487349 -708917766
-446575764 -920302303
373857024 -525302786
236159958 -877034512
240035307 -28559828
-156425976 29793081
-683968223 -28559828
658545653 -892201965
-485118423 -349005511
-677465608 102959577
-241309351 -615266668
-857580103 -877034512
590882873 69859569
-961101806 -2385646...

output:

454
795 300
4 406
391 535
638 61
671 712
67 726
27 532
119 376
99 482
327 844
856 339
212 127
318 315
265 338
215 86
667 683
609 635
760 781
503 271
298 574
778 167
121 659
240 568
596 68
687 351
640 137
262 506
864 675
696 564
95 708
660 762
91 700
765 47
759 388
346 241
382 784
837 148
898 737
450...

result:

ok ok (100 test cases)

Test #41:

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

input:

100
140
229220674 878836488
-506767178 293730975
960642833 878836488
485659386 878836488
-225376185 16183205
-322465048 -460955536
-635701181 878836488
-578723152 374559636
956924322 878836488
-666563369 -550449367
-240963901 374559636
9519098 374559636
404598294 16183205
-188062738 467646265
937074...

output:

140
47 15
16 3
43 107
72 242
9 118
57 149
197 252
81 253
48 103
163 185
259 93
37 219
238 41
13 178
248 271
98 74
173 166
158 132
208 246
176 21
265 228
114 56
233 106
102 223
76 140
221 255
55 235
156 30
34 35
232 186
224 236
155 215
180 247
258 277
157 117
122 33
25 279
261 159
42 50
138 65
27 101...

result:

ok ok (100 test cases)

Test #42:

score: -100
Time Limit Exceeded

input:

100
453
-9728842 -879506383
723264369 -879506383
-617602947 -879506383
-883543546 -879506383
-365459776 -879506383
259863014 -879506383
-229024413 -879506383
-357634378 -879506383
45613473 -879506383
897413515 -879506383
142722904 -879506383
308356916 -879506383
-528467703 -879506383
45803942 -87950...

output:

453
43 688
457 214
694 462
691 421
78 131
393 585
891 203
841 537
699 634
44 456
449 707
488 899
729 497
250 623
150 787
129 331
295 683
654 641
205 506
355 871
763 40
660 637
10 757
113 83
655 875
692 307
581 513
266 602
531 176
168 337
70 64
664 753
249 470
148 371
76 450
225 619
709 397
696 721
8...

result: