QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#189947#3309. Sewing GraphKKT89AC ✓1ms4236kbC++17927b2023-09-28 01:46:332023-09-28 01:46:33

Judging History

This is the latest submission verdict.

  • [2023-09-28 01:46:33]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4236kb
  • [2023-09-28 01:46:33]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<int> x(n),y(n);
	map<pair<int,int>,int> mp;
	map<int,vector<int>> v;
	for(int i=0;i<n;i++){
		cin >> x[i] >> y[i];
		mp[make_pair(x[i],y[i])]=i+1;
		v[x[i]].push_back(y[i]);
	}
	vector<int> res;
	vector<int> vv;
	for(auto &p:v){
		sort(p.second.begin(), p.second.end());
		vv.push_back(p.first);
	}
	for(int i=0;i<vv.size();i++){
		vector<int> vvv;
		for(int j=0;j<v[vv[i]].size();j++){
			res.push_back(mp[make_pair(vv[i],v[vv[i]][j])]);
			vvv.push_back(res.back());
		}
		for(int j=(int)(vvv.size())-2;j>=0;j--){
			res.push_back(vvv[j]);
		}
	}
	for(int i=(int)vv.size()-2;i>=0;i--){
		res.push_back(mp[make_pair(vv[i],v[vv[i]][0])]);
	}
	printf("%d\n",res.size());
	for(int p:res){
		printf("%d ",p);
	}
	printf("\n");
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3760kb

input:

5
1 1
2 4
3 2
4 5
5 3

output:

9
1 2 3 4 5 4 3 2 1 

result:

ok n=5

Test #2:

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

input:

2
1 1
1 2

output:

3
1 2 1 

result:

ok n=2

Test #3:

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

input:

10
5 2
1 3
3 3
5 3
2 5
1 1
4 1
4 2
4 5
3 4

output:

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

result:

ok n=10

Test #4:

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

input:

11
691 541
958 300
997 873
218 109
776 271
500 118
653 29
10 34
132 16
517 916
175 526

output:

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

result:

ok n=11

Test #5:

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

input:

12
316603600 584499138
9018553 396885280
79748988 538870870
725373218 444191298
168824727 872885053
718145129 927234173
962954960 294542779
112179693 752174357
400742230 57133365
482755026 597968817
27647072 875133876
592311678 792195806

output:

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

result:

ok n=12

Test #6:

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

input:

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

output:

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

result:

ok n=50

Test #7:

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

input:

51
46 512
17 665
259 218
846 455
588 980
499 764
367 19
911 890
211 74
972 739
781 549
378 911
687 167
187 729
380 276
277 2
398 15
99 85
577 318
756 961
85 313
939 131
39 342
805 161
312 808
894 295
413 179
900 150
557 90
786 216
398 218
295 358
897 660
429 442
209 830
394 325
816 171
170 306
643 6...

output:

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

result:

ok n=51

Test #8:

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

input:

52
820255036 223063699
667690661 601051988
341310690 421475708
625599123 34567585
954575436 40580613
75597208 477662527
936181311 900135194
442276299 78704572
296158025 981549322
297983820 773944907
87235638 738834955
123623098 383433281
55585436 968354996
641321403 16812441
908631888 753518721
4042...

output:

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

result:

ok n=52

Test #9:

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

input:

200
18 2
19 3
16 17
5 14
16 18
13 10
8 7
19 10
17 17
4 6
7 6
15 6
11 14
20 11
7 15
13 16
7 8
20 10
13 11
19 1
13 6
18 4
16 12
16 7
3 12
3 18
4 4
7 20
9 11
12 14
12 3
1 9
11 17
20 3
20 7
9 14
18 13
9 17
16 3
17 4
10 17
5 20
3 8
17 11
12 7
19 14
19 4
16 6
5 3
15 14
3 14
20 18
14 16
15 15
13 4
6 19
19 ...

output:

399
162 78 69 159 77 87 137 32 150 100 115 100 150 32 137 87 77 159 69 78 162 99 93 71 152 158 152 71 93 99 190 96 92 43 151 194 25 63 51 26 121 193 121 26 51 63 25 194 151 43 92 96 190 112 27 10 97 186 106 72 106 186 97 10 27 112 59 49 187 169 65 122 76 160 4 118 119 66 130 42 130 66 119 118 4 160 ...

result:

ok n=200

Test #10:

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

input:

201
875 762
316 846
182 883
206 870
154 341
966 3
618 187
97 224
112 43
228 380
765 741
747 75
255 991
396 973
653 860
281 958
301 984
322 724
663 302
305 773
640 146
148 398
624 392
230 532
916 707
966 55
980 326
14 50
6 15
213 269
281 495
14 275
699 555
15 908
180 166
899 772
121 621
320 906
114 1...

output:

401
29 43 144 28 32 28 34 99 44 99 137 86 189 68 58 66 52 42 8 56 89 9 39 80 37 166 109 82 129 22 129 110 55 110 196 5 114 103 71 181 162 188 200 35 69 35 3 152 173 152 154 118 154 45 4 167 30 167 171 151 10 24 81 168 13 168 48 183 180 146 134 31 16 31 122 17 122 143 128 20 128 143 176 153 176 195 2...

result:

ok n=201

Test #11:

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

input:

202
761119100 799926411
3720523 6989350
429080158 39281459
38602478 369989753
594005622 686280947
254712108 595317496
214831567 286896539
592549795 773447764
65438393 925187295
844734580 806501732
805763143 268330199
733810371 70824865
16279248 59678847
587349306 101801898
519761007 622507064
551435...

output:

403
138 2 68 119 13 164 73 136 4 101 123 185 197 102 155 16 45 9 25 85 22 18 162 114 189 199 147 32 171 65 182 38 122 193 184 163 50 21 196 198 48 113 7 41 37 190 111 6 137 61 84 17 125 90 103 83 40 187 141 64 175 145 63 133 30 176 57 86 34 87 134 152 36 126 195 124 159 154 174 78 96 167 161 130 39 ...

result:

ok n=202

Test #12:

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

input:

1000
10 47
5 12
18 10
2 16
7 27
8 5
4 10
9 13
20 25
8 28
18 21
9 23
14 47
14 48
1 44
18 5
10 31
17 31
15 33
19 3
15 10
19 17
5 19
11 12
10 35
5 36
2 40
10 49
20 11
2 47
19 40
5 15
3 26
14 37
18 50
11 8
3 35
12 34
20 49
16 42
7 22
5 35
5 45
5 34
7 18
4 16
8 36
5 42
6 40
5 31
2 35
12 29
1 23
15 7
7 14...

output:

1999
480 660 627 499 873 131 845 601 878 803 63 800 94 388 426 272 140 884 987 653 830 522 53 308 744 893 806 178 355 119 190 865 182 97 174 392 488 844 798 832 240 692 895 15 501 290 666 542 330 244 330 542 666 290 501 15 895 692 240 832 798 844 488 392 174 97 182 865 190 119 355 178 806 893 744 30...

result:

ok n=1000

Test #13:

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

input:

1000
55 3
20 4
94 5
24 6
58 9
27 5
1 5
15 8
47 4
76 10
54 3
94 1
99 4
33 1
85 9
40 5
17 9
73 3
46 2
9 7
51 5
12 5
76 5
11 2
86 6
3 8
89 6
79 6
14 10
42 8
51 7
77 10
56 1
68 4
72 3
71 5
12 7
20 5
40 1
93 4
13 2
65 1
32 5
35 9
22 1
34 1
62 3
95 4
65 7
56 5
93 3
44 4
37 10
32 7
64 3
55 5
78 4
80 2
82 6...

output:

1999
459 358 206 259 7 289 318 213 252 207 252 213 318 289 7 259 206 358 459 879 835 174 347 696 871 331 964 588 813 588 964 331 871 696 347 174 835 879 466 869 336 115 561 180 817 26 507 202 507 26 817 180 561 115 336 869 466 361 122 819 509 551 622 446 352 220 880 220 352 446 622 551 509 819 122 3...

result:

ok n=1000

Test #14:

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

input:

1000
1 595
1 308
1 350
1 695
1 485
1 649
1 265
1 445
1 93
1 486
1 884
1 805
1 317
1 960
1 567
1 921
1 456
1 791
1 871
1 18
1 55
1 529
1 431
1 69
1 959
1 738
1 915
1 375
1 45
1 663
1 999
1 33
1 289
1 277
1 806
1 298
1 154
1 197
1 12
1 326
1 824
1 30
1 346
1 722
1 76
1 361
1 293
1 818
1 719
1 957
1 78...

output:

1999
518 562 948 847 441 266 432 406 805 74 947 39 609 538 780 557 954 20 593 161 370 440 912 877 643 682 482 460 795 42 901 388 32 804 477 600 894 114 420 555 311 364 705 230 29 534 684 291 798 875 962 759 377 889 21 500 189 68 844 221 284 162 918 599 755 718 354 621 24 903 698 931 195 271 745 45 9...

result:

ok n=1000

Test #15:

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

input:

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

output:

1999
195 804 612 38 267 137 947 319 318 239 557 146 513 874 538 674 538 874 513 146 557 239 318 319 947 137 267 38 612 804 195 193 888 93 422 962 506 120 650 481 767 865 486 410 471 231 395 496 949 323 473 721 23 472 418 472 23 721 473 323 949 496 395 231 471 410 486 865 767 481 650 120 506 962 422 ...

result:

ok n=1000

Test #16:

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

input:

999
948 434
755 608
794 739
419 938
160 794
841 868
743 801
885 623
504 353
989 90
954 19
984 182
904 227
316 273
976 519
936 148
732 724
139 365
469 170
899 614
371 51
135 556
422 528
510 720
217 700
710 929
665 382
230 769
658 812
627 660
938 691
655 868
636 464
109 47
719 554
431 343
245 669
848 ...

output:

1997
925 981 995 719 778 719 392 486 313 486 392 994 588 994 915 907 647 907 932 592 637 900 97 358 736 358 598 864 598 117 752 245 947 572 410 193 410 59 814 971 974 407 853 533 253 881 978 707 53 707 115 930 115 478 807 478 910 307 910 928 827 928 210 882 615 882 210 58 259 225 661 266 661 225 259...

result:

ok n=999

Test #17:

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

input:

998
751459 151634
44776 864932
199344 595783
759047 300118
275775 437745
301376 814308
539011 831880
577434 652649
918835 902120
160668 47715
654665 159250
183445 286132
128518 359338
674261 743393
799404 496695
141105 184535
112771 564325
594562 511201
408021 744006
958374 92531
600113 570637
90463...

output:

1995
905 787 814 287 984 56 166 604 128 269 131 625 674 734 501 76 941 967 481 223 933 920 708 737 791 272 176 330 317 560 673 376 295 305 686 774 115 649 763 264 919 75 473 159 582 792 225 172 782 484 622 406 916 815 2 679 817 258 175 778 238 600 847 139 983 439 557 651 852 589 988 636 735 577 561 ...

result:

ok n=998

Test #18:

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

input:

1000
556753360 794327018
150116472 212403895
885211063 908402611
776190453 982300031
837010658 43115997
709411772 123047318
114175953 16115870
225778499 505972853
382021643 67378895
689971007 741742710
41589399 597258351
143289901 299212635
68182659 93630752
594259146 196764360
331501409 110463656
7...

output:

1999
354 84 376 72 537 894 643 801 79 279 207 344 718 779 349 574 901 562 274 309 126 762 859 461 604 130 60 184 335 319 856 705 994 120 733 735 151 341 334 384 899 357 426 378 11 834 199 59 94 81 163 895 182 500 678 799 830 146 332 921 826 939 603 936 692 417 478 174 755 137 689 242 13 161 877 329 ...

result:

ok n=1000