QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300598 | #7861. Inverse Topological Sort | willow# | AC ✓ | 62ms | 17748kb | C++14 | 1.8kb | 2024-01-08 14:53:09 | 2024-01-08 14:53:09 |
Judging History
你现在查看的是测评时间为 2024-01-08 14:53:09 的历史记录
- [2024-11-22 19:52:53]
- hack成功,自动添加数据
- (/hack/1241)
- [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: 8956kb
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: 9868kb
input:
3 1 2 3 3 2 1
output:
Yes 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 9000kb
input:
3 3 2 1 1 2 3
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 9984kb
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: 1ms
memory: 9600kb
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: 1ms
memory: 9456kb
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: 9844kb
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: 59ms
memory: 16688kb
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: 53ms
memory: 15944kb
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: 34ms
memory: 15532kb
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: 59ms
memory: 16340kb
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: 56ms
memory: 16596kb
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: 62ms
memory: 15928kb
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: 58ms
memory: 17748kb
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: 39ms
memory: 15868kb
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: 31ms
memory: 15688kb
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: 34ms
memory: 16568kb
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: 40ms
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: 27ms
memory: 16496kb
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: 34ms
memory: 16720kb
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: 8568kb
input:
1 1 1
output:
Yes 0
result:
ok n=1
Extra Test:
score: 0
Extra Test Passed