QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771551#7861. Inverse Topological SortguanzyAC ✓29ms8192kbC++14804b2024-11-22 14:06:152024-11-22 19:55:20

Judging History

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

  • [2024-11-22 19:55:20]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:29ms
  • 内存:8192kb
  • [2024-11-22 19:52:53]
  • hack成功,自动添加数据
  • (/hack/1241)
  • [2024-11-22 14:06:15]
  • 评测
  • 测评结果:100
  • 用时:28ms
  • 内存:8140kb
  • [2024-11-22 14:06:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n,a[200010],b[200010],pa[200010],pb[200010],sta[200010],cnt;
vector<pair<int,int> >e;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),pa[a[i]]=i;
	for(int i=1;i<=n;i++) scanf("%d",&b[i]),pb[b[i]]=i;
	for(int i=1;i<=n;i++){
		while(cnt&&a[sta[cnt]]<a[i]) cnt--;
		if(cnt) e.push_back({a[sta[cnt]],a[i]});
		sta[++cnt]=i;
	}cnt=0;
	for(int i=1;i<=n;i++){
		while(cnt&&b[sta[cnt]]>b[i]) cnt--;
		if(cnt) e.push_back({b[sta[cnt]],b[i]});
		sta[++cnt]=i;
	}
	for(int i=0;i<e.size();i++){
		if(pa[e[i].first]>pa[e[i].second]||pb[e[i].first]>pb[e[i].second]){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes\n"<<e.size()<<endl;
	for(int i=0;i<e.size();i++){
		printf("%d %d\n",e[i].first,e[i].second);
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

3
1 2 3
1 2 3

output:

Yes
2
1 2
2 3

result:

ok n=3

Test #2:

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

input:

3
1 2 3
3 2 1

output:

Yes
0

result:

ok n=3

Test #3:

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

input:

3
3 2 1
1 2 3

output:

No

result:

ok n=3

Test #4:

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

input:

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

output:

Yes
10
9 4
4 1
4 3
9 7
7 5
10 2
6 9
9 10
4 7
4 5

result:

ok n=10

Test #5:

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

input:

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

output:

Yes
6
4 2
9 1
9 3
7 9
1 10
1 3

result:

ok n=10

Test #6:

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

input:

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

output:

Yes
148
36 28
46 2
46 38
48 23
48 29
48 30
48 31
31 12
48 40
83 14
83 68
83 74
83 79
88 56
56 6
56 39
92 9
92 11
11 4
92 47
47 3
47 13
47 15
15 8
92 49
92 54
54 32
54 45
92 61
61 33
92 66
92 72
92 80
80 24
80 69
92 89
89 21
89 82
94 27
94 76
94 90
90 10
90 18
90 77
90 78
78 57
95 7
95 50
95 81
97 35...

result:

ok n=100

Test #7:

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

input:

1000
11 2 29 50 53 54 155 162 211 213 223 240 270 226 243 276 288 304 315 341 249 358 359 381 178 402 51 417 434 163 459 466 471 498 327 464 518 527 549 559 113 581 589 60 347 594 504 593 598 603 607 610 619 648 649 658 681 684 416 686 153 712 575 741 349 382 759 322 17 289 763 764 774 718 777 9 637...

output:

Yes
1830
11 2
270 226
270 243
341 249
381 178
402 51
434 163
498 327
498 464
559 113
589 60
589 347
594 504
594 593
684 416
686 153
712 575
741 349
741 382
759 322
322 17
322 289
774 718
777 9
777 637
808 68
808 390
808 437
843 502
843 505
505 41
505 409
843 690
849 806
859 605
605 194
859 633
889 3...

result:

ok n=1000

Test #8:

score: 0
Accepted
time: 20ms
memory: 7124kb

input:

100000
1 5 10 12 13 14 16 17 18 19 21 27 28 33 37 40 41 44 45 49 50 51 52 54 57 58 62 64 67 69 71 72 74 75 77 78 79 80 84 89 93 95 96 100 102 104 111 113 115 117 118 119 120 121 122 123 124 126 127 129 132 135 136 138 139 142 144 150 151 152 153 154 155 156 164 166 167 170 174 177 178 180 181 182 18...

output:

Yes
78810
879 331
1678 362
2038 1937
2574 1981
2639 2143
2737 99
2737 810
2915 2621
3528 558
3673 1890
3681 918
3797 857
3879 697
3906 714
3906 1291
4029 1040
4070 556
4143 2245
4204 226
4215 1841
4220 2406
4225 2938
4390 3338
4507 1567
4571 252
4607 1258
4721 2637
4844 2926
5121 3463
5169 2628
5198...

result:

ok n=100000

Test #9:

score: 0
Accepted
time: 27ms
memory: 8056kb

input:

100000
40 84 102 116 124 157 177 191 193 199 256 259 293 300 304 326 430 439 473 477 489 511 515 518 547 583 593 630 664 697 747 751 769 787 789 892 928 945 963 971 978 1052 1063 1067 1077 1080 1088 1101 1136 1143 1172 1180 1198 1274 1312 1359 1361 1380 1382 1404 1414 1428 1435 1466 1475 1497 1517 1...

output:

Yes
183695
2282 1882
4001 1479
4089 357
5025 4177
5650 818
5661 4309
7190 2459
7790 3669
7807 1299
8114 1326
8171 5811
5811 2778
8891 6966
9281 3652
9449 2277
9532 4670
10071 5112
10215 3787
10558 4576
10819 6416
10901 7175
11143 2117
12247 6807
12336 729
12367 5668
12860 425
12860 6385
14102 1863
1...

result:

ok n=100000

Test #10:

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

input:

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

output:

Yes
1988
1577 1183
2149 890
5479 4107
5573 3401
6683 3857
7485 6847
7506 3898
9329 1743
10005 3653
10672 1175
10782 881
11058 8313
11174 3482
11201 10937
11339 9081
11841 2515
12627 4848
13288 4924
14096 1310
14579 10262
14669 2993
15339 7699
15549 10894
15651 1867
16289 14449
16316 10197
16381 7518...

result:

ok n=100000

Test #11:

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

input:

100000
4 6 12 16 20 23 24 27 32 34 36 39 46 54 68 76 77 81 86 88 95 99 103 107 112 113 117 120 125 140 142 143 149 158 161 167 171 174 176 187 190 192 195 198 200 206 207 211 217 222 226 227 231 233 239 240 241 245 247 249 264 274 275 276 277 280 288 290 296 303 305 312 321 329 333 336 338 339 341 3...

output:

Yes
122343
1558 587
3016 936
3065 1681
3815 1666
4079 1240
4285 3905
4354 132
4355 3249
4366 3927
4410 812
4502 3261
4520 3392
4654 864
4767 1767
4776 3172
5122 4411
5356 3432
5561 4175
5594 5141
5629 1696
5733 354
5945 3692
5965 5366
5992 4820
6312 2915
2915 1997
6475 4312
6528 6172
6710 498
6722 3...

result:

ok n=100000

Test #12:

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

input:

100000
1 2 4 5 6 7 10 13 14 15 16 20 21 22 24 25 26 28 29 30 31 33 34 35 36 37 38 39 40 43 44 45 46 47 48 51 52 55 56 57 58 59 62 65 66 67 68 69 70 71 72 73 74 75 76 77 78 80 81 82 85 87 89 91 92 93 94 97 98 99 100 101 102 103 104 105 106 107 111 112 113 115 117 119 120 121 123 124 128 130 132 133 1...

output:

Yes
44465
383 83
1131 546
1634 1587
1661 468
1730 544
1925 928
1955 1101
2167 1916
2179 992
2192 978
2420 353
2455 364
2491 2174
2868 607
3015 929
3041 2761
3198 2013
3282 1493
3325 377
3328 1018
3495 901
3499 656
3547 1520
3574 2653
3617 2002
3619 1696
3630 2800
3655 1184
3803 2012
4082 541
4255 34...

result:

ok n=100000

Test #13:

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

input:

100000
33 43 47 65 67 82 88 95 96 113 130 133 140 232 262 266 282 286 298 299 303 324 326 342 352 354 356 359 362 363 364 369 392 398 408 435 442 454 460 489 508 518 537 556 572 574 580 592 613 616 629 650 652 674 684 718 721 724 732 734 801 809 819 831 845 853 856 878 879 895 897 935 946 956 958 96...

output:

Yes
167027
1045 109
1929 812
2111 657
2497 781
2497 1419
2738 1918
2804 2000
3051 2747
3186 1791
4099 1828
4813 2663
4862 4199
4911 1334
4974 74
5011 481
5435 321
6232 5767
7094 5660
7150 3353
7280 153
7981 4404
8303 5309
8340 2309
8362 2456
8515 7392
8570 5945
8634 6381
8810 4900
9060 479
9069 6588...

result:

ok n=100000

Test #14:

score: 0
Accepted
time: 24ms
memory: 7944kb

input:

100000
38535 3433 18670 53850 31420 79252 3155 90709 7043 47690 20905 66663 16655 77812 19606 78158 23549 54025 44700 24119 42542 85555 31117 68856 35627 37419 26767 46031 72252 71511 80835 47732 77030 61434 51792 98165 71334 70644 79996 87007 93335 56112 86306 3040 10776 30683 80961 96794 12323 656...

output:

Yes
199973
38535 3433
38535 18670
53850 31420
79252 3155
90709 7043
90709 47690
47690 20905
90709 66663
66663 16655
90709 77812
77812 19606
90709 78158
78158 23549
78158 54025
54025 44700
44700 24119
44700 42542
90709 85555
85555 31117
85555 68856
68856 35627
68856 37419
37419 26767
68856 46031
8555...

result:

ok n=100000

Test #15:

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

input:

100000
1 5 7 8 24 29 32 36 39 41 43 44 46 47 52 54 56 58 59 64 68 69 70 73 75 77 79 82 84 86 88 90 92 93 95 98 99 101 102 104 105 108 112 114 115 116 118 123 126 127 128 133 134 139 140 143 145 147 152 153 154 156 160 161 163 165 169 170 176 178 179 180 184 186 187 188 192 193 195 199 200 204 205 20...

output:

No

result:

ok n=100000

Test #16:

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

input:

100000
1 3 4 7 10 11 13 17 18 19 21 22 25 27 28 29 31 35 36 37 38 42 49 50 53 56 57 58 60 62 63 64 68 70 71 79 80 82 83 85 86 87 88 90 93 94 98 103 105 109 110 111 112 116 121 123 127 134 138 139 142 143 148 151 154 156 158 159 160 162 164 166 168 171 172 173 174 175 176 177 180 184 186 187 189 193 ...

output:

No

result:

ok n=100000

Test #17:

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

input:

100000
1 2 8 9 11 14 19 21 22 24 25 28 33 34 35 36 43 49 51 55 57 59 62 64 68 69 70 71 72 75 76 78 79 80 81 82 83 87 88 89 91 92 98 99 105 106 107 111 112 116 118 123 124 125 128 131 133 138 139 141 142 143 146 147 152 154 155 159 161 162 163 164 165 169 172 173 174 175 179 183 184 185 186 187 190 1...

output:

No

result:

ok n=100000

Test #18:

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

input:

100000
60 134 140 182 208 256 291 327 364 395 404 419 439 444 457 469 486 510 527 561 569 595 611 612 645 654 710 778 792 794 810 832 873 890 900 901 911 914 942 946 978 1022 1057 1060 1083 1094 1095 1146 1154 1155 1280 1323 1336 1368 1379 1388 1395 1480 1500 1509 1548 1573 1580 1597 1601 1622 1629 ...

output:

No

result:

ok n=100000

Test #19:

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

input:

100000
52072 2 3 50731 5 75525 49404 8 52753 2744 11 34189 13 48355 15 16 17 50376 86416 20 21 56114 23 20072 25 53838 48273 63338 29 30 60156 6205 8084 34 35 36 48381 71655 72484 63969 88506 59722 27083 5369 44672 86160 39926 48 49 8962 51 47113 53 69142 55 66271 24245 74454 59 72556 61 35930 86895...

output:

No

result:

ok n=100000

Test #20:

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

input:

100000
13821 33496 19412 85158 61916 61576 41795 39637 42402 12256 37931 7198 19499 24983 15918 19942 56948 7239 17886 24328 17628 63213 4681 90112 37749 17984 25778 75577 33274 43479 47779 64385 77793 82833 15116 96895 87829 30340 25506 7179 48585 77809 44101 91839 93597 69594 37840 3271 4541 68178...

output:

No

result:

ok n=100000

Test #21:

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

input:

1
1
1

output:

Yes
0

result:

ok n=1

Extra Test:

score: 0
Extra Test Passed