QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#440044#5565. Mirror Madnesstz3528AC ✓192ms77456kbC++202.2kb2024-06-13 00:32:282024-06-13 00:32:29

Judging History

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

  • [2024-06-13 00:32:29]
  • 评测
  • 测评结果：AC
  • 用时：192ms
  • 内存：77456kb
查看
  • [2024-06-13 00:32:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct point {
	int x,y,left,right,val;
	bool operator<(point b)const{
		return x<b.x;
	}
};
vector<point> p[2000010],q[2000010];
void solve(){
	int n,m;
	cin>>n>>m;
	point start,last,now;
	cin>>now.x>>now.y;
	start=now;
	for(int i=2;i<=n+1;i++){
		last=now;
		if(i<=n) cin>>now.x>>now.y;
		else now=start;
		if(last.x==now.x){
			if(last.y<=now.y){
				for(int j=last.y+1;j<now.y;j++) {
					point a;a.x=now.x;a.y=j;a.val=1;
					p[a.x+a.y+maxn].push_back(a);
					q[a.x-a.y+maxn].push_back(a);
				}
			}
			else {
				for(int j=last.y-1;j>now.y;j--) {
					point a;a.x=now.x;a.y=j;a.val=1;
					p[a.x+a.y+maxn].push_back(a);
					q[a.x-a.y+maxn].push_back(a);
				}
			}
		}
		else {
			if(last.x<=now.x){
				for(int j=last.x+1;j<now.x;j++) {
					point a;a.x=j;a.y=now.y;a.val=0;
					p[a.x+a.y+maxn].push_back(a);
					q[a.x-a.y+maxn].push_back(a);
				}
			}
			else {
				for(int j=last.x-1;j>now.x;j--) {
					point a;a.x=j;a.y=now.y;a.val=0;
					p[a.x+a.y+maxn].push_back(a);
					q[a.x-a.y+maxn].push_back(a);
				}
			}
		}
	}
	for(int i=0;i<=2000000;i++){
		sort(p[i].begin(),p[i].end());
		sort(q[i].begin(),q[i].end());
	}
	int flag=1;
	cin>>start.x>>start.y;
	for(int i=1;i<=m;i++){
		if(flag==1){
			int sum=start.x-start.y+maxn;
			int k=lower_bound(q[sum].begin(),q[sum].end(),start)-q[sum].begin();
			start=q[sum][k+1];
			if(start.val==1) flag=3;
			else flag=2;
		}
		else if(flag==2){
			int sum=start.x+start.y+maxn;
			int k=lower_bound(p[sum].begin(),p[sum].end(),start)-p[sum].begin();
			start=p[sum][k+1];
			if(start.val==1) flag=4;
			else flag=1;
		}
		else if(flag==3){
			int sum=start.x+start.y+maxn;
			int k=lower_bound(p[sum].begin(),p[sum].end(),start)-p[sum].begin();
			start=p[sum][k-1];
			if(start.val==1) flag=1;
			else flag=4;
		}
		else if(flag==4){
			int sum=start.x-start.y+maxn;
			int k=lower_bound(q[sum].begin(),q[sum].end(),start)-q[sum].begin();
			start=q[sum][k-1];
			if(start.val==1) flag=2;
			else flag=3;
		}
		cout<<start.x<<" "<<start.y<<"\n";
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 3524kb

input:

4 6
0 0
10 0
10 10
0 10
1 0

output:

10 9
9 10
0 1
1 0
10 9
9 10

result:

ok 6 lines

Test #2:

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

input:

10 10
-2 -2
8 -2
8 8
4 8
4 0
2 0
2 6
-4 6
-4 2
-2 2
4 1

output:

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

result:

ok 10 lines

Test #3:

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

input:

20 50
0 0
18 0
18 10
16 10
16 2
14 2
14 10
12 10
12 2
10 2
10 10
8 10
8 2
6 2
6 10
4 10
4 2
2 2
2 10
0 10
1 0

output:

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

result:

ok 50 lines

Test #4:

score: 0
Accepted
time: 106ms
memory: 49796kb

input:

1996 500000
0 0
1994 0
1994 1000
1992 1000
1992 2
1990 2
1990 1000
1988 1000
1988 2
1986 2
1986 1000
1984 1000
1984 2
1982 2
1982 1000
1980 1000
1980 2
1978 2
1978 1000
1976 1000
1976 2
1974 2
1974 1000
1972 1000
1972 2
1970 2
1970 1000
1968 1000
1968 2
1966 2
1966 1000
1964 1000
1964 2
1962 2
1962 ...

output:

3 2
5 0
7 2
9 0
11 2
13 0
15 2
17 0
19 2
21 0
23 2
25 0
27 2
29 0
31 2
33 0
35 2
37 0
39 2
41 0
43 2
45 0
47 2
49 0
51 2
53 0
55 2
57 0
59 2
61 0
63 2
65 0
67 2
69 0
71 2
73 0
75 2
77 0
79 2
81 0
83 2
85 0
87 2
89 0
91 2
93 0
95 2
97 0
99 2
101 0
103 2
105 0
107 2
109 0
111 2
113 0
115 2
117 0
119 2...

result:

ok 500000 lines

Test #5:

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

input:

333332 500000
0 0
333330 0
333330 4
333328 4
333328 2
333326 2
333326 4
333324 4
333324 2
333322 2
333322 4
333320 4
333320 2
333318 2
333318 4
333316 4
333316 2
333314 2
333314 4
333312 4
333312 2
333310 2
333310 4
333308 4
333308 2
333306 2
333306 4
333304 4
333304 2
333302 2
333302 4
333300 4
333...

output:

3 2
5 0
7 2
9 0
11 2
13 0
15 2
17 0
19 2
21 0
23 2
25 0
27 2
29 0
31 2
33 0
35 2
37 0
39 2
41 0
43 2
45 0
47 2
49 0
51 2
53 0
55 2
57 0
59 2
61 0
63 2
65 0
67 2
69 0
71 2
73 0
75 2
77 0
79 2
81 0
83 2
85 0
87 2
89 0
91 2
93 0
95 2
97 0
99 2
101 0
103 2
105 0
107 2
109 0
111 2
113 0
115 2
117 0
119 2...

result:

ok 500000 lines

Test #6:

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

input:

340 3000
2 0
2 -2
4 -2
4 0
6 0
6 2
8 2
8 4
10 4
10 2
12 2
12 0
14 0
14 2
16 2
16 0
18 0
18 -2
20 -2
20 -4
22 -4
22 -6
24 -6
24 -4
26 -4
26 -6
28 -6
28 -4
30 -4
30 -2
32 -2
32 -4
34 -4
34 -6
36 -6
36 -8
38 -8
38 -10
40 -10
40 -8
42 -8
42 -10
44 -10
44 -8
46 -8
46 -10
48 -10
48 -12
50 -12
50 -14
52 -1...

output:

44 -9
3 32
2 31
3 30
32 59
31 60
4 33
45 -8
108 55
107 56
42 -9
43 -10
44 -9
3 32
2 31
3 30
32 59
31 60
4 33
45 -8
108 55
107 56
42 -9
43 -10
44 -9
3 32
2 31
3 30
32 59
31 60
4 33
45 -8
108 55
107 56
42 -9
43 -10
44 -9
3 32
2 31
3 30
32 59
31 60
4 33
45 -8
108 55
107 56
42 -9
43 -10
44 -9
3 32
2 31
...

result:

ok 3000 lines

Test #7:

score: 0
Accepted
time: 89ms
memory: 41444kb

input:

499996 50000
2 0
2 -2
4 -2
4 0
6 0
6 -2
8 -2
8 -4
10 -4
10 -2
12 -2
12 -4
14 -4
14 -6
16 -6
16 -8
18 -8
18 -6
20 -6
20 -4
22 -4
22 -2
24 -2
24 -4
26 -4
26 -2
28 -2
28 -4
30 -4
30 -2
32 -2
32 0
34 0
34 2
36 2
36 4
38 4
38 2
40 2
40 4
42 4
42 6
44 6
44 4
46 4
46 6
48 6
48 8
50 8
50 10
52 10
52 8
54 8
...

output:

124868 71163
124867 71164
53412 -291
53413 -292
53414 -291
-21 53144
-22 53143
53409 -288
124864 71167
71235 124796
71234 124795
124869 71160
124870 71161
124869 71162
53416 -291
53417 -292
53418 -291
-21 53148
-22 53147
-21 53146
71642 124809
71641 124810
-18 53151
53421 -288
124868 71159
71233 124...

result:

ok 50000 lines

Test #8:

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

input:

499996 500000
2 0
2 -2
4 -2
4 -4
6 -4
6 -2
8 -2
8 -4
10 -4
10 -2
12 -2
12 0
14 0
14 2
16 2
16 4
18 4
18 2
20 2
20 4
22 4
22 2
24 2
24 4
26 4
26 6
28 6
28 8
30 8
30 6
32 6
32 4
34 4
34 2
36 2
36 4
38 4
38 2
40 2
40 4
42 4
42 6
44 6
44 4
46 4
46 2
48 2
48 0
50 0
50 2
52 2
52 0
54 0
54 2
56 2
56 4
58 4...

output:

23678 93
-295 24066
-296 24065
23673 96
80350 56773
-61 137184
-62 137183
80351 56770
80352 56771
80351 56772
23674 95
23675 94
80350 56769
-63 137182
-64 137181
80357 56760
80358 56761
80357 56762
23692 97
23693 96
23694 97
-299 24090
-300 24089
23689 100
80354 56765
80353 56766
23682 95
23683 94
2...

result:

ok 500000 lines

Test #9:

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

input:

82 250
0 0
2 0
2 4
4 4
4 0
26 0
26 10
16 10
16 6
10 6
10 8
14 8
14 12
18 12
18 16
28 16
28 14
20 14
20 12
34 12
34 16
36 16
36 12
44 12
44 6
38 6
38 8
42 8
42 10
28 10
28 0
46 0
46 2
34 2
34 6
32 6
32 2
30 2
30 8
36 8
36 4
46 4
46 18
40 18
40 16
44 16
44 14
38 14
38 18
32 18
32 14
30 14
30 18
4 18
4...

output:

11 10
13 8
14 9
12 11
15 14
17 12
18 13
16 15
19 18
21 16
23 18
25 16
27 18
30 15
27 12
25 14
23 12
21 14
20 13
21 12
23 14
25 12
27 14
29 12
31 14
33 12
34 13
32 15
35 18
38 15
36 13
37 12
39 14
41 12
43 14
46 11
44 9
46 7
43 4
41 6
39 4
36 7
39 10
41 8
42 9
41 10
39 8
37 10
35 8
33 10
31 8
29 10
2...

result:

ok 250 lines

Test #10:

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

input:

216 98765
-78 -32
-64 -32
-64 -24
-44 -24
-44 -20
-38 -20
-38 -30
-60 -30
-60 -32
-28 -32
-28 -24
-26 -24
-26 -32
-16 -32
-16 -20
-14 -20
-14 -32
-8 -32
-8 -20
-4 -20
-4 -32
6 -32
6 -16
20 -16
20 -2
6 -2
6 14
-4 14
-4 8
-10 8
-10 -14
-16 -14
-16 0
-14 0
-14 -4
-12 -4
-12 22
-10 22
-10 10
-8 10
-8 22...

output:

-71 -30
-69 -32
-64 -27
-68 -23
-67 -22
-64 -25
-68 -29
-65 -32
-64 -31
-68 -27
-63 -22
-61 -24
-59 -22
-57 -24
-55 -22
-53 -24
-51 -22
-49 -24
-47 -22
-45 -24
-44 -23
-46 -21
-43 -18
-41 -20
-39 -18
-36 -21
-38 -23
-36 -25
-38 -27
-36 -29
-39 -32
-41 -30
-43 -32
-45 -30
-47 -32
-49 -30
-51 -32
-53 ...

result:

ok 98765 lines

Test #11:

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

input:

174078 500000
0 0
2 0
2 12
4 12
4 0
10 0
10 4
14 4
14 8
16 8
16 2
12 2
12 0
26 0
26 4
38 4
38 8
50 8
50 12
54 12
54 18
44 18
44 14
28 14
28 10
22 10
22 22
14 22
14 28
18 28
18 32
24 32
24 30
20 30
20 26
16 26
16 24
46 24
46 28
50 28
50 32
52 32
52 26
48 26
48 22
40 22
40 18
30 18
30 20
38 20
38 22
2...

output:

497 554
498 553
496 551
499 548
502 551
500 553
502 555
500 557
502 559
499 562
496 559
498 557
497 556
495 558
493 556
492 557
494 559
492 561
494 563
491 566
489 564
487 566
485 564
483 566
481 564
479 566
477 564
476 565
478 567
475 570
473 568
471 570
469 568
468 569
470 571
467 574
465 572
463 ...

result:

ok 500000 lines

Test #12:

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

input:

87166 500000
-990 -1000
-988 -1000
-988 -952
-964 -952
-964 -954
-972 -954
-972 -964
-980 -964
-980 -974
-972 -974
-972 -994
-962 -994
-962 -968
-954 -968
-954 -962
-950 -962
-950 -954
-954 -954
-954 -952
-950 -952
-950 -940
-954 -940
-954 -930
-962 -930
-962 -924
-980 -924
-980 -938
-972 -938
-972 ...

output:

208 -685
205 -682
203 -684
196 -677
203 -670
204 -671
196 -679
201 -684
204 -681
193 -670
189 -674
185 -670
175 -680
171 -676
167 -680
164 -677
166 -675
164 -673
166 -671
164 -669
166 -667
165 -666
163 -668
158 -663
162 -659
158 -655
161 -652
162 -653
158 -657
162 -661
158 -665
161 -668
163 -666
166...

result:

ok 500000 lines

Test #13:

score: 0
Accepted
time: 26ms
memory: 4284kb

input:

4 200000
0 0
3240 0
3240 1428
0 1428
3239 0

output:

3240 1
1813 1428
385 0
0 385
1043 1428
2471 0
3240 769
2581 1428
1153 0
0 1153
275 1428
1703 0
3131 1428
3240 1319
1921 0
493 1428
0 935
935 0
2363 1428
3240 551
2689 0
1261 1428
0 167
167 0
1595 1428
3023 0
3240 217
2029 1428
601 0
0 601
827 1428
2255 0
3240 985
2797 1428
1369 0
0 1369
59 1428
1487...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 111ms
memory: 74044kb

input:

4 500000
0 0
249998 0
249998 250000
0 250000
249997 0

output:

249998 1
0 249999
1 250000
249998 3
249995 0
0 249995
5 250000
249998 7
249991 0
0 249991
9 250000
249998 11
249987 0
0 249987
13 250000
249998 15
249983 0
0 249983
17 250000
249998 19
249979 0
0 249979
21 250000
249998 23
249975 0
0 249975
25 250000
249998 27
249971 0
0 249971
29 250000
249998 31
2...

result:

ok 500000 lines

Test #15:

score: 0
Accepted
time: 192ms
memory: 77456kb

input:

4 500000
0 0
391622 0
391622 108378
0 108378
391621 0

output:

391622 1
283245 108378
174867 0
66489 108378
0 41889
41889 0
150267 108378
258645 0
367023 108378
391622 83779
307843 0
199465 108378
91087 0
0 91087
17291 108378
125669 0
234047 108378
342425 0
391622 49197
332441 108378
224063 0
115685 108378
7307 0
0 7307
101071 108378
209449 0
317827 108378
3916...

result:

ok 500000 lines

Test #16:

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

input:

36 4000
0 0
50 0
50 34
0 34
0 4
46 4
46 30
4 30
4 8
42 8
42 26
8 26
8 12
38 12
38 22
12 22
12 16
34 16
34 18
14 18
14 20
36 20
36 14
10 14
10 24
40 24
40 10
6 10
6 28
44 28
44 6
2 6
2 32
48 32
48 2
0 2
44 27

output:

46 29
45 30
43 28
41 30
39 28
37 30
35 28
33 30
31 28
29 30
27 28
25 30
23 28
21 30
19 28
17 30
15 28
13 30
11 28
9 30
7 28
5 30
4 29
6 27
4 25
6 23
4 21
6 19
4 17
6 15
4 13
6 11
4 9
5 8
7 10
9 8
11 10
13 8
15 10
17 8
19 10
21 8
23 10
25 8
27 10
29 8
31 10
33 8
35 10
37 8
39 10
41 8
42 9
40 11
42 13...

result:

ok 4000 lines

Test #17:

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

input:

32 5000
4 116
6102 116
6102 2116
4 2116
4 448
5202 448
5202 1760
464 1760
464 584
4718 584
4718 1722
564 1722
564 844
4628 844
4628 1540
722 1540
722 1510
4516 1510
4516 1116
662 1116
662 1636
4704 1636
4704 588
484 588
484 1748
4790 1748
4790 470
168 470
168 1818
5708 1818
5708 316
4 316
4077 1510

output:

4107 1540
4137 1510
4167 1540
4197 1510
4227 1540
4257 1510
4287 1540
4317 1510
4347 1540
4377 1510
4407 1540
4437 1510
4467 1540
4497 1510
4527 1540
4628 1439
4516 1327
4628 1215
4257 844
3985 1116
3713 844
3441 1116
3169 844
2897 1116
2625 844
2353 1116
2081 844
1809 1116
1537 844
1265 1116
993 84...

result:

ok 5000 lines

Test #18:

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

input:

500 500000
0 0
3998 0
3998 498
0 498
0 4
3994 4
3994 494
4 494
4 8
3990 8
3990 490
8 490
8 12
3986 12
3986 486
12 486
12 16
3982 16
3982 482
16 482
16 20
3978 20
3978 478
20 478
20 24
3974 24
3974 474
24 474
24 28
3970 28
3970 470
28 470
28 32
3966 32
3966 466
32 466
32 36
3962 36
3962 462
36 462
36...

output:

2259 154
2261 152
2263 154
2265 152
2267 154
2269 152
2271 154
2273 152
2275 154
2277 152
2279 154
2281 152
2283 154
2285 152
2287 154
2289 152
2291 154
2293 152
2295 154
2297 152
2299 154
2301 152
2303 154
2305 152
2307 154
2309 152
2311 154
2313 152
2315 154
2317 152
2319 154
2321 152
2323 154
232...

result:

ok 500000 lines

Test #19:

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

input:

858 500000
2 2
1704 2
1704 2062
2 2062
2 8
1694 8
1694 2052
14 2052
14 14
1674 14
1674 2046
20 2046
20 22
1670 22
1670 2034
32 2034
32 26
1666 26
1666 2026
36 2026
36 32
1654 32
1654 2020
40 2020
40 50
1650 50
1650 2016
50 2016
50 56
1644 56
1644 2006
58 2006
58 62
1638 62
1638 1992
64 1992
64 66
16...

output:

336 1499
334 1501
336 1503
334 1505
336 1507
334 1509
336 1511
334 1513
336 1515
334 1517
336 1519
334 1521
336 1523
334 1525
336 1527
334 1529
336 1531
334 1533
336 1535
334 1537
336 1539
334 1541
336 1543
334 1545
336 1547
334 1549
336 1551
334 1553
336 1555
334 1557
336 1559
334 1561
336 1563
334...

result:

ok 500000 lines

Test #20:

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

input:

66 100
0 0
4 0
4 2
6 2
6 4
8 4
8 6
10 6
10 8
12 8
12 10
14 10
14 12
16 12
16 14
18 14
18 16
20 16
20 18
22 18
22 20
24 20
24 22
26 22
26 24
28 24
28 26
30 26
30 28
32 28
32 30
34 30
34 34
32 34
32 32
30 32
30 30
28 30
28 28
26 28
26 26
24 26
24 24
22 24
22 22
20 22
20 20
18 20
18 18
16 18
16 16
14 1...

output:

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

result:

ok 100 lines

Test #21:

score: 0
Accepted
time: 122ms
memory: 38348kb

input:

499998 500000
0 0
4 0
4 2
6 2
6 4
8 4
8 6
10 6
10 8
12 8
12 10
14 10
14 12
16 12
16 14
18 14
18 16
20 16
20 18
22 18
22 20
24 20
24 22
26 22
26 24
28 24
28 26
30 26
30 28
32 28
32 30
34 30
34 32
36 32
36 34
38 34
38 36
40 36
40 38
42 38
42 40
44 40
44 42
46 42
46 44
48 44
48 46
50 46
50 48
52 48
52 ...

output:

250000 249999
249999 250000
249998 249999
250000 249997
249999 249996
249997 249998
249996 249997
249998 249995
249997 249994
249995 249996
249994 249995
249996 249993
249995 249992
249993 249994
249992 249993
249994 249991
249993 249990
249991 249992
249990 249991
249992 249989
249991 249988
249989...

result:

ok 500000 lines
English 繁體中文 简体中文

Server Time: 2024-11-30 07:44:52 | OpenSource Project