QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300598#7861. Inverse Topological Sortwillow#AC ✓94ms17944kbC++141.8kb2024-01-08 14:53:092024-11-22 19:54:15

Judging History

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

  • [2024-11-22 19:54:15]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:94ms
  • 内存:17944kb
  • [2024-11-22 19:52:53]
  • hack成功,自动添加数据
  • (/hack/1241)
  • [2024-01-08 14:53:09]
  • 评测
  • 测评结果:100
  • 用时:62ms
  • 内存:17748kb
  • [2024-01-08 14:53:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, a[maxn], b[maxn], df[maxn], dg[maxn], tp[maxn], tot;
vector<pair<int, int> > edges;
vector<int>F[maxn], G[maxn];
set<int> s;
void Add(int u, int v) {
	edges.push_back({u, v});
	G[u].push_back(v);
	++ dg[v];
	F[u].push_back(v);
	++ df[v];
}
priority_queue<int, vector<int>, greater<int> > qg;
int Topo1() {
	tot = 0;
	for(int i = 1; i <= n; ++ i) {
		if(!dg[i])
			qg.push(i);
	}
	while(!qg.empty()) {
		int u = qg.top();
		tp[++ tot] = u;
		qg.pop();
		for(auto v : G[u]) {
			if(!(-- dg[v])) {
				qg.push(v);
			}
		}
	}
	if(tot < n)
		return 0;
	for(int i = 1; i <= n; ++ i)
		if(tp[i] != a[i])
			return 0;
	return 1;
}
priority_queue<int> qf;
int Topo2() {
	tot = 0;
	for(int i = 1; i <= n; ++ i) {
		if(!df[i])
			qf.push(i);
	}
	while(!qf.empty()) {
		int u = qf.top();
		tp[++ tot] = u;
		qf.pop();
		for(auto v : F[u]) {
			if(!(-- df[v])) {
				qf.push(v);
			}
		}
	}
	if(tot < n)
		return 0;
	for(int i = 1; i <= n; ++ i)
		if(tp[i] != b[i])
			return 0;
	return 1;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &b[i]);
	}
	s.clear();
	for(int i = n; i; -- i) {
		while(s.size() && *s.begin() < a[i]) {
			Add(a[i], *s.begin());
			s.erase(s.begin());
		}
		s.insert(a[i]);
	}
	s.clear();
	for(int i = n; i; -- i) {
		while(s.size() && *prev(s.end()) > b[i]) {
			Add(b[i], *prev(s.end()));
			s.erase(prev(s.end()));
		}
		s.insert(b[i]);
	}
	if(!Topo1())
		return 0 * puts("No");
	if(!Topo2())
		return 0 * puts("No");
	puts("Yes");
	printf("%d\n", (int)edges.size());
	for(auto [u, v] : edges)
		printf("%d %d\n", u, v);
}

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

详细

Test #1:

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

input:

3
1 2 3
1 2 3

output:

Yes
2
2 3
1 2

result:

ok n=3

Test #2:

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

input:

3
1 2 3
3 2 1

output:

Yes
0

result:

ok n=3

Test #3:

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

input:

3
3 2 1
1 2 3

output:

No

result:

ok n=3

Test #4:

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

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
10 2
7 5
4 1
4 3
9 4
9 7
4 7
4 5
9 10
6 9

result:

ok n=10

Test #5:

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

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
9 1
9 3
4 2
1 10
1 3
7 9

result:

ok n=10

Test #6:

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

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
100 17
99 59
98 1
98 41
98 70
62 53
85 37
85 62
65 43
91 65
91 85
73 52
67 22
63 34
63 60
44 20
35 19
97 35
97 44
97 55
97 63
97 67
97 73
97 87
97 91
95 7
95 50
95 81
78 57
90 10
90 18
90 77
90 78
94 27
94 76
94 90
89 21
89 82
80 24
80 69
61 33
54 32
54 45
15 8
47 3
47 13
47 15
11 4
92 9
92 ...

result:

ok n=100

Test #7:

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

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
964 761
987 281
987 570
987 623
987 964
325 316
967 325
850 164
850 362
850 710
850 714
850 733
722 184
722 419
472 386
411 335
962 87
962 373
962 411
962 469
962 472
962 664
962 722
962 850
330 166
949 330
949 630
949 734
737 42
960 39
960 71
960 95
960 109
960 232
960 429
960 522
960 577
...

result:

ok n=1000

Test #8:

score: 0
Accepted
time: 76ms
memory: 16752kb

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
99998 2607
99995 5256
99995 10082
86766 21242
99993 86766
99993 99344
46540 4651
99991 2968
99991 4876
99991 46540
27653 16291
99989 22159
99989 27653
99986 39630
99986 95606
99984 11668
99984 38367
99983 48570
99981 80197
66928 38060
99980 2970
99980 22585
99980 29394
99980 30230
99980 66...

result:

ok n=100000

Test #9:

score: 0
Accepted
time: 65ms
memory: 15956kb

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
43215 30876
100000 43215
100000 43719
100000 99174
99989 97376
33913 19300
98911 33913
94168 27637
94168 41535
94168 86836
96803 21059
96803 92580
96803 94168
73604 1090
73604 66126
61462 19504
25451 21209
98465 1468
98465 25451
98465 28391
98465 37320
98465 51063
98465 61462
98465 69442
...

result:

ok n=100000

Test #10:

score: 0
Accepted
time: 42ms
memory: 15560kb

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
99961 79316
99948 60152
99943 35307
99923 93649
99880 3930
99875 33000
99875 99582
99872 18134
99845 83506
99684 48619
99573 73025
99562 6110
99535 79511
99510 98320
99486 55606
99375 72298
99344 88821
99310 39188
99294 47587
99261 88410
99230 31623
99218 13512
99183 36965
99021 81585
99005...

result:

ok n=100000

Test #11:

score: 0
Accepted
time: 77ms
memory: 16364kb

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
93656 21513
93656 22365
93656 25985
96246 34121
96246 53327
96246 78224
96246 93656
100000 351
100000 1932
100000 50999
100000 54593
100000 64255
100000 79251
100000 96246
100000 98816
19073 16367
99999 83
99999 19073
26358 22169
49984 26358
99998 16733
99998 47303
99998 49984
99998 53907...

result:

ok n=100000

Test #12:

score: 0
Accepted
time: 71ms
memory: 16644kb

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
99999 60442
99999 95873
99996 30948
99993 11115
99993 62013
99992 22454
99989 17285
99989 18139
99989 64558
99981 10113
99977 38292
99976 481
99976 9128
99976 29076
99976 45126
99972 62469
99972 71057
99962 67964
99961 75120
89923 23653
89923 75961
99956 89923
91455 10940
99955 91455
99951...

result:

ok n=100000

Test #13:

score: 0
Accepted
time: 94ms
memory: 16220kb

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
33624 589
100000 33624
53414 5442
98058 50429
98058 53414
91710 33838
91710 89716
83406 36364
87046 83406
84332 44752
81546 13802
81546 37972
65859 13695
65859 48637
24828 4424
24828 4934
24828 14105
99999 24828
99999 58123
99999 63064
99999 65449
99999 65859
99999 81546
99999 84332
99999...

result:

ok n=100000

Test #14:

score: 0
Accepted
time: 80ms
memory: 17944kb

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
46455 27992
67655 3778
67655 46455
90549 67655
52916 22889
67387 52916
69931 37840
69931 62530
69931 67387
95824 69931
95824 90549
99136 27234
99136 95824
74028 18751
74028 62257
74263 19068
74263 74028
26584 5670
26584 13275
59418 9761
59418 11699
59418 26584
59418 43709
57289 51895
5728...

result:

ok n=100000

Test #15:

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

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: 36ms
memory: 15744kb

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: 31ms
memory: 16252kb

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: 55ms
memory: 15728kb

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: 39ms
memory: 16568kb

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: 44ms
memory: 16756kb

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: 3ms
memory: 10380kb

input:

1
1
1

output:

Yes
0

result:

ok n=1

Extra Test:

score: 0
Extra Test Passed