QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353761#7861. Inverse Topological Sortucup-team3215AC ✓26ms5320kbC++201.1kb2024-03-14 15:59:212024-11-22 19:54:35

Judging History

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

  • [2024-11-22 19:54:35]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:26ms
  • 内存:5320kb
  • [2024-11-22 19:52:53]
  • hack成功,自动添加数据
  • (/hack/1241)
  • [2024-03-14 15:59:22]
  • 评测
  • 测评结果:100
  • 用时:27ms
  • 内存:5288kb
  • [2024-03-14 15:59:21]
  • 提交

answer

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

using namespace std;

constexpr int N = 1e5;

array<int, 2> anc[N];

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n; cin >> n;
  fill(anc[0].begin(), anc[N].begin(), -1);
  vector<int> up(n), down(n), st, hv(n);
  for (auto& x: up) {
    cin >> x, --x;
    while (st.size() && st.back() < x) st.pop_back();
    if (st.size()) anc[x][0] = st.back();
    st.push_back(x);
  }
  st.clear();
  for (auto& x: down) {
    cin >> x, --x;
    while (st.size() && st.back() > x) st.pop_back();
    hv[x] = 1;
    if (~anc[x][0] && !hv[anc[x][0]]) return cout << "No\n", 0;
    if (st.size()) anc[x][!!~anc[x][0]] = st.back();
    st.push_back(x);
  }
  fill(hv.begin(), hv.end(), 0);
  for (auto& x: up) {
    hv[x] = 1;
    for (auto y: anc[x]) if (~y && !hv[y]) return cout << "nO\n", 0;
  }
  cout << "Yes\n";
  int ans = 0;
  for (int i = 0; i < n; ++i) for (auto j: anc[i]) if (~j) ++ans;
  cout << ans << '\n';
  for (int i = 0; i < n; ++i) for (auto j: anc[i]) if (~j) cout << j + 1 << ' ' << i + 1 << '\n';
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4404kb

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: 0ms
memory: 4336kb

input:

3
1 2 3
3 2 1

output:

Yes
0

result:

ok n=3

Test #3:

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

input:

3
3 2 1
1 2 3

output:

No

result:

ok n=3

Test #4:

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

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

result:

ok n=10

Test #5:

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

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

result:

ok n=10

Test #6:

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

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
98 1
46 2
47 3
2 3
11 4
56 6
95 7
2 7
15 8
2 8
92 9
90 10
8 10
92 11
31 12
47 13
2 13
83 14
47 15
2 15
100 17
3 17
90 18
8 18
35 19
8 19
44 20
3 20
89 21
15 21
67 22
19 22
48 23
80 24
4 24
94 27
8 27
36 28
26 28
48 29
23 29
48 30
48 31
54 32
9 32
61 33
2 33
63 34
7 34
97 35
8 35
85 37
3 37
4...

result:

ok n=100

Test #7:

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

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
914 1
11 2
554 3
2 3
983 4
2 4
627 5
2 5
181 6
2 6
713 7
2 7
708 8
2 8
777 9
149 10
228 12
3 12
379 13
3 13
698 14
966 15
11 15
995 16
322 17
503 18
2 18
921 19
5 19
500 20
7 20
206 21
2 21
968 22
11 22
326 23
2 23
679 24
7 24
321 25
7 25
487 26
3 26
944 27
3 27
225 28
3 28
953 30
7 30
296 ...

result:

ok n=1000

Test #8:

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

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
73188 2
80951 3
98808 4
49585 6
50809 7
30111 8
29805 9
26311 11
67311 15
71079 20
28642 22
97354 23
62104 24
99521 25
34645 26
27900 29
94743 30
97249 31
72536 32
96704 34
29284 35
51795 36
88880 38
51927 39
76152 42
99439 43
79265 46
92105 47
87943 48
53791 53
34711 55
88201 56
76586 59
...

result:

ok n=100000

Test #9:

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

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
89688 1
79915 2
1 2
33226 3
65358 4
62079 5
89179 6
84009 7
23330 8
1 8
35695 9
15472 10
1 10
33082 11
3 11
98106 12
6952 13
38184 14
52142 15
1 15
99614 16
95982 17
89426 18
85514 19
12 19
58630 20
98602 21
48071 22
3 22
60954 23
3 23
56524 24
57167 25
12 25
88427 26
12 26
85749 27
56729...

result:

ok n=100000

Test #10:

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

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
38447 15
65055 42
74459 160
73673 174
21219 276
26846 403
79939 417
58255 455
80736 540
10782 881
2149 890
89916 946
43865 970
20837 1141
10672 1175
1577 1183
50553 1251
22597 1275
89316 1281
14096 1310
33457 1449
79720 1571
83859 1700
9329 1743
47809 1764
57680 1842
83603 1853
15651 1867
9...

result:

ok n=100000

Test #11:

score: 0
Accepted
time: 22ms
memory: 5252kb

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
25629 1
25430 2
91057 3
71937 5
73314 7
48687 8
56935 9
25290 10
16978 11
15579 13
57774 14
62568 15
69166 17
20846 18
81085 19
80758 21
99979 22
97046 25
91448 26
34138 28
7984 29
60463 30
52300 31
14248 33
63172 35
26648 37
9935 38
99250 40
62129 41
95162 42
64627 43
57746 44
70336 45
9...

result:

ok n=100000

Test #12:

score: 0
Accepted
time: 15ms
memory: 5296kb

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
27267 3
99900 8
76990 9
59088 11
37208 12
52637 17
10821 18
52803 19
78175 23
77020 27
98435 32
35814 41
12125 42
41122 49
31747 50
99027 53
70620 54
92204 60
72721 61
24699 63
22786 64
3641 79
383 83
92898 84
91243 86
56423 88
86484 90
46644 95
41502 96
86871 108
16620 109
41065 110
66120...

result:

ok n=100000

Test #13:

score: 0
Accepted
time: 22ms
memory: 5152kb

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
18853 1
99600 2
59123 3
41679 4
22507 5
59011 6
69670 7
96323 8
49985 9
45594 10
35374 11
94830 12
22008 13
9840 14
50505 15
4688 16
25860 17
62707 18
66615 19
10075 20
6 20
51480 21
97282 22
56889 23
7 23
75094 24
69647 25
6 25
98251 26
99103 27
2607 28
22 28
96088 29
72954 30
29653 31
3...

result:

ok n=100000

Test #14:

score: 0
Accepted
time: 23ms
memory: 5156kb

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
24612 1
49035 2
1 2
98378 3
2 3
74525 4
2 4
12659 5
4 5
344 6
97157 7
2 7
84388 8
1 8
46138 9
2 9
98873 10
3 10
69326 11
71999 12
3 12
21521 13
12 13
13244 14
81987 15
3 15
5151 16
11 16
22882 17
5 17
63736 18
11 18
79627 19
14 19
54601 20
6 20
54820 21
17 21
91691 22
17 22
37135 23
1 23
...

result:

ok n=100000

Test #15:

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

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: 6ms
memory: 5184kb

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: 6ms
memory: 5140kb

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: 6ms
memory: 5296kb

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

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

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: 4404kb

input:

1
1
1

output:

Yes
0

result:

ok n=1

Extra Test:

score: 0
Extra Test Passed