QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #445686 | #8528. Chords | ucup-team3924 | TL | 2715ms | 29260kb | C++20 | 2.6kb | 2024-06-16 08:03:30 | 2024-06-16 08:03:31 |
Judging History
answer
#include <bits/stdc++.h>
int dist(int a, int b, int N) {
if (a <= b) return b - a;
return N - (a - b);
}
int main() {
std::cin.tie(NULL);
std::iostream::sync_with_stdio(false);
int N;
std::cin >> N;
std::vector<int> link(2 * N);
for (int i = 0; i < N; i++) {
int x, y;
std::cin >> x >> y;
x--;y--;
link[x] = y;
link[y] = x;
}
std::vector<std::vector<int>> dp(2 * N, std::vector<int>(1, -1));
for (int i = 0; i < 2 * N; i++) {
dp[i][0] = i;
dp[i].reserve(100);
}
int res = 0, ans = 1;
bool compute = true;
while (compute) {
for (int i = 0; i < 2 * N; i++)
dp[i].push_back(-1);
for (int i = 0; i < 2 * N; i++) {
int j = link[i];
int x = (i + 1) % (2 * N);
int y = dp[x][ans - 1];
if (ans == 1)
dp[i][ans] = j;
else if (y != -1 && dist(i, j, 2 * N) == dist(i, x, 2 * N) + dist(x, y, 2 * N) + dist(y, j, 2 * N)) {
dp[i][ans] = j;
}
}
for (int i = 0; i < 2 * N; i++) {
if (dp[i][ans - 1] == -1) continue;
for (int ansp = 1; ansp < ans; ansp++) {
int j = dp[i][ansp];
if (j == -1) continue;
int x = (j + 1);
if (x == 2 * N)
x = 0;
int y = dp[x][ans - ansp];
if (x != i && y != i && y != -1 && dist(j, i, 2 * N) == dist(j, x, 2 * N) + dist(x, y, 2 * N) + dist(y, i, 2 * N)) {
if (dp[i][ans] == -1)
dp[i][ans] = y;
else if (dist(i, y, 2 * N) <= dist(i, dp[i][ans], 2 * N))
dp[i][ans] = y;
}
}
}
for (int _i = 4 * N - 1; _i >= 0; _i--) {
int i = _i % (2 * N);
int inext = (i + 1) % (2 * N);
if (dp[i][ans] == -1 && dp[inext][ans] != i)
dp[i][ans] = dp[inext][ans];
else if (dp[inext][ans] != -1 && dp[inext][ans] != i && dist(i, dp[inext][ans], 2 * N) <= dist(i, dp[i][ans], 2 * N))
dp[i][ans] = dp[inext][ans];
}
//std::cerr << ans << ": \n";
compute = false;
for (int i = 0; i < 2 * N; i++)
if (dp[i][ans] != -1) {
res = ans;
compute = true;
//std::cerr << i + 1 << " -> " << dp[ans][i] + 1 << "\n";
}
ans++;
}
std::cout << res;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
5 1 2 4 10 7 9 3 5 6 8
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
2 1 3 2 4
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
2 1 4 2 3
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 3 5 1 4 2 6
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
4 2 7 1 6 3 8 4 5
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
6 8 9 6 7 4 10 1 5 11 12 2 3
output:
5
result:
ok 1 number(s): "5"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
9 2 8 10 17 9 15 1 12 6 14 3 13 4 11 5 7 16 18
output:
4
result:
ok 1 number(s): "4"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
13 8 16 2 13 14 23 10 11 7 17 6 24 12 18 9 20 4 15 19 21 3 26 1 25 5 22
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
19 34 35 4 20 9 31 12 17 18 38 23 29 19 30 25 26 10 36 1 7 13 37 2 11 8 32 6 28 16 24 5 27 14 21 15 22 3 33
output:
8
result:
ok 1 number(s): "8"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
28 9 45 7 19 15 40 42 44 26 31 20 22 16 55 6 34 41 56 28 51 2 33 36 53 3 13 37 52 4 46 12 48 21 27 24 30 23 38 1 32 8 14 43 54 11 17 47 49 29 35 5 25 18 39 10 50
output:
10
result:
ok 1 number(s): "10"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
42 2 66 29 75 5 45 8 53 50 72 25 44 15 47 6 57 64 68 26 80 32 49 65 70 27 54 37 58 18 36 10 48 3 63 28 60 30 76 16 41 7 83 21 24 14 17 31 67 62 71 20 74 11 33 43 84 40 61 19 69 35 82 13 42 34 79 12 73 9 51 4 23 77 81 22 59 1 52 39 55 38 56 46 78
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
63 40 105 6 104 45 83 16 22 31 34 51 57 64 92 75 112 70 82 65 121 32 93 18 60 30 68 72 77 86 101 10 47 85 94 36 71 11 35 27 126 56 74 15 52 19 91 88 110 76 97 25 33 58 109 42 54 12 26 73 107 99 118 29 106 44 90 3 9 23 122 14 79 87 116 4 81 17 111 41 53 50 123 38 124 13 114 67 96 5 100 55 115 43 62 4...
output:
17
result:
ok 1 number(s): "17"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
94 109 118 69 152 93 185 111 162 17 188 15 175 35 123 13 95 72 186 83 160 52 117 24 159 128 163 56 179 141 168 25 58 44 82 47 53 78 172 100 105 70 106 143 164 4 88 99 182 98 146 57 77 38 112 91 149 45 174 125 138 26 34 37 121 62 134 97 187 2 66 22 40 153 181 86 108 19 155 33 130 103 177 11 21 18 126...
output:
21
result:
ok 1 number(s): "21"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
141 31 127 1 73 84 94 158 254 129 208 35 114 112 201 182 222 18 259 27 267 67 271 14 160 22 269 89 161 57 58 49 86 8 184 202 256 24 43 194 198 225 273 204 265 79 270 66 249 54 250 130 268 26 162 165 261 197 257 119 279 216 232 21 274 151 179 106 140 28 48 122 206 65 186 3 177 90 92 15 105 163 262 14...
output:
32
result:
ok 1 number(s): "32"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
211 101 338 116 315 84 296 142 211 22 419 260 266 157 261 231 360 95 100 27 111 286 409 355 372 50 348 97 178 39 349 153 217 63 203 236 289 156 278 37 311 40 306 282 384 113 240 168 365 5 89 190 322 71 414 77 191 10 325 87 357 321 376 370 380 207 362 30 165 9 170 128 287 43 398 56 180 310 335 42 70 ...
output:
29
result:
ok 1 number(s): "29"
Test #17:
score: 0
Accepted
time: 5ms
memory: 3980kb
input:
316 433 483 190 220 85 439 171 209 459 479 4 63 335 434 315 400 55 155 125 558 457 619 90 187 135 301 172 497 124 354 101 363 140 312 288 425 99 513 147 516 120 122 143 180 138 500 78 617 123 191 231 615 268 536 227 417 32 67 360 554 263 553 108 165 105 257 295 620 95 212 21 319 87 464 356 559 266 6...
output:
45
result:
ok 1 number(s): "45"
Test #18:
score: 0
Accepted
time: 10ms
memory: 3748kb
input:
474 177 498 736 821 556 671 366 896 11 519 110 409 282 813 219 355 516 562 395 893 388 436 52 767 174 490 627 911 23 796 280 468 724 947 367 371 324 872 484 578 125 163 93 218 549 916 272 649 694 704 86 716 420 508 569 905 329 805 386 433 32 175 169 898 6 809 456 659 688 914 143 803 405 506 103 682 ...
output:
53
result:
ok 1 number(s): "53"
Test #19:
score: 0
Accepted
time: 18ms
memory: 4076kb
input:
711 394 512 506 1310 203 763 470 1161 548 1183 94 383 131 1123 467 478 141 695 969 1128 210 211 1045 1236 1184 1258 536 658 53 1174 115 687 648 911 410 735 266 732 226 1300 646 826 952 1019 353 1387 60 533 972 1221 418 1360 162 677 166 981 730 1130 859 1414 252 365 129 515 258 581 214 1290 1133 1289...
output:
61
result:
ok 1 number(s): "61"
Test #20:
score: 0
Accepted
time: 48ms
memory: 4196kb
input:
1066 1612 1799 593 928 560 965 683 1118 1058 1221 664 879 696 1724 54 102 1580 1588 599 1444 796 1749 35 1831 1 1261 299 1420 607 1048 147 643 873 1405 450 1080 1310 1489 1029 1658 183 752 666 1797 211 1485 51 802 42 673 1484 1811 540 561 934 1869 571 2081 1070 1248 362 1149 641 740 1540 1755 1329 1...
output:
82
result:
ok 1 number(s): "82"
Test #21:
score: 0
Accepted
time: 96ms
memory: 4528kb
input:
1599 668 1208 169 1885 106 2776 28 96 812 2453 2216 3175 783 2096 1005 1448 1430 1831 1252 3133 957 2070 2278 3096 747 1967 1765 2448 2377 2694 1522 1993 529 1006 329 771 130 1634 2057 2243 1222 3030 410 2565 1654 2264 1117 1387 1168 2360 2292 2848 1386 1460 2101 2124 671 3156 2215 2829 637 2782 20 ...
output:
95
result:
ok 1 number(s): "95"
Test #22:
score: 0
Accepted
time: 203ms
memory: 7016kb
input:
2398 3145 4490 88 211 1400 3788 3415 3441 889 3689 731 2304 2530 3700 2336 4449 3760 4420 2858 2932 1950 3588 1225 4526 1090 3288 521 2786 2196 4509 1057 2779 138 4514 882 3907 1393 3478 476 996 1410 4368 167 937 716 1773 458 4070 2527 4059 23 653 2720 4233 504 733 3367 3967 985 4483 300 918 1210 29...
output:
112
result:
ok 1 number(s): "112"
Test #23:
score: 0
Accepted
time: 573ms
memory: 9148kb
input:
3597 1586 6330 130 6292 3020 3385 874 5423 727 3192 329 2042 1352 2951 622 3427 4344 5462 2152 3104 521 5655 3682 5793 2324 2452 559 2822 4260 4634 4549 5092 245 2665 4872 5563 4717 5574 1909 2400 1456 4161 1546 3255 4454 5449 1027 4348 1083 4115 4715 6687 2093 6654 1851 4449 2731 4648 52 6819 2174 ...
output:
155
result:
ok 1 number(s): "155"
Test #24:
score: 0
Accepted
time: 1285ms
memory: 12040kb
input:
5395 6550 9543 608 6746 1809 2339 3025 7758 1781 3543 6472 8170 6599 6801 5698 10446 1004 1449 6068 8618 1783 3263 2553 10510 4676 7024 5560 8498 5187 9289 1406 9596 7180 9101 6262 6534 964 8578 128 3469 1429 8001 3289 10484 5369 6694 680 4256 2086 4761 3936 4069 5487 8704 1580 9873 1600 10687 5555 ...
output:
189
result:
ok 1 number(s): "189"
Test #25:
score: 0
Accepted
time: 2715ms
memory: 29260kb
input:
8092 1215 1887 813 12062 6710 9368 3227 3301 3923 9087 10036 11031 4632 13551 6161 13621 11190 12323 1993 14422 1012 15346 9369 11317 10356 11487 6181 14543 9245 10856 6898 10739 9132 11811 4357 5662 10216 11646 10857 14436 4238 7756 4359 5479 10547 13421 10704 11950 1089 2415 12928 13119 4629 5742 ...
output:
222
result:
ok 1 number(s): "222"
Test #26:
score: -100
Time Limit Exceeded
input:
12138 7599 9917 3613 15148 11028 19684 1426 22404 11772 12554 5840 19850 7493 23645 10133 18786 7322 11394 7703 22318 12434 21398 12972 13383 4041 7101 778 8840 5943 6841 7964 22934 4228 4919 14952 22462 9113 11699 20909 22889 3146 22742 9506 13307 42 5163 12325 15531 14618 15980 473 9087 4510 11886...