QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#374423 | #6396. Puzzle: Kusabi | ricofx | AC ✓ | 34ms | 41764kb | C++17 | 4.1kb | 2024-04-02 14:13:11 | 2024-04-02 14:13:11 |
Judging History
answer
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int N = 1e5 + 5;
int n, w[N], dep[N];
vector<int> G[N];
vector<pii> ans;
pii dfs(int u) {
vector<int> d[3];
for (int v : G[u]) {
dep[v] = dep[u] + 1;
auto t = dfs(v);
if (t.fi != 0) d[t.fi - 1].push_back(t.se);
}
if (w[u]) d[w[u] - 1].push_back(u);
for (int i = 0; i < 3; i++) sort(d[i].begin(), d[i].end(), [](int x, int y) {
return dep[x] < dep[y];
});
int cnt = 0, lst = 0, lp = 0, idx = 0;
for (int i = 0; i <= d[0].size(); i++) {
if ((i == d[0].size()) || (i != 0 && dep[d[0][i]] != dep[d[0][i - 1]])) {
for (int j = lp; j + 1 < i; j += 2) {
ans.push_back({d[0][j + 1], d[0][j]});
//cerr << d[0].size() << ' '<< j << ' ' << d[0][j + 1] << ' ' << d[0][j] << '\n';
}
if (lst & 1) idx = d[0][i - 1], ++cnt;
lst = 0, lp = i;
}
++lst;
}
if (abs((int)d[1].size() - (int)d[2].size()) + cnt > 1) {cout << "NO\n" << '\n' ; exit(0);}
int m = min(d[1].size(), d[2].size());
if (d[1].size() == d[2].size()) {
for (int i = 0; i < m; i++) if (dep[d[1][i]] >= dep[d[2][i]]) {cout << "NO\n"; exit(0);}
for (int i = 0; i < m; i++) ans.push_back({d[1][i], d[2][i]});
} else if (d[1].size() > d[2].size()) {
if (m == 0) return {2, d[1][0]};
vector<int> pre(m, 1), suf(m, 1);
pre[0] = (dep[d[1][0]] < dep[d[2][0]]);
for (int i = 1; i < m; i++) pre[i] = (pre[i - 1] && (dep[d[1][i]] < dep[d[2][i]]));
suf[m - 1] = (dep[d[1].back()] < dep[d[2].back()]);
for (int i = m - 2; i >= 0; i--) suf[i] = (suf[i + 1] && dep[d[2][i]] > dep[d[1][i + 1]]);
int pos = -1;
for (int i = 0; i < d[1].size(); i++) {
int check = ((i == 0 && suf[0]) || (i + 1 == d[1].size() && pre[m - 1]) ||
(i > 0 && i + 1 < d[1].size() && pre[i - 1] && suf[i]));
if (check) {
pos = i;
break;
}
}
if (pos == -1) {cout << "NO\n"; exit(0);}
for (int p = 0, q = 0; p < m; p++, q++) {
if (q == pos) ++q;
ans.push_back({d[2][p], d[1][q]});
}
return {2, d[1][pos]};
} else {
swap(d[1], d[2]);
if (m == 0) return {3, d[1][0]};
vector<int> pre(m, 1), suf(m, 1);
pre[0] = (dep[d[1][0]] > dep[d[2][0]]);
for (int i = 1; i < m; i++) pre[i] = (pre[i - 1] && (dep[d[1][i]] > dep[d[2][i]]));
suf[m - 1] = (dep[d[1].back()] > dep[d[2].back()]);
for (int i = m - 2; i >= 0; i--) suf[i] = (suf[i + 1] && dep[d[2][i]] < dep[d[1][i + 1]]);
int pos = -1;
for (int i = 0; i < d[1].size(); i++) {
int check = ((i == 0 && suf[0]) || (i + 1 == d[1].size() && pre[m - 1]) ||
(i > 0 && i + 1 < d[1].size() && pre[i - 1] && suf[i]));
if (check) pos = i;
}
if (pos == -1) {cout << "NO\n"; exit(0);}
for (int p = 0, q = 0; p < m; p++, q++) {
if (q == pos) ++q;
ans.push_back({d[2][p], d[1][q]});
}
return {3, d[1][pos]};
}
return cnt == 1 ? (pii){1, idx} : (pii){0, 0};
}
void MAIN() {
cin >> n;
for (int i = 2; i <= n; i++) {
int u, v;
static string t;
cin >> u >> v >> t;
G[v].push_back(u);
w[i] = t == "-" ? 0 : t == "Tong" ? 1 : t == "Duan" ? 2 : 3;
}
auto t = dfs(1);
if (t.fi != 0) return cout << "NO\n", void();
cout << "YES\n";
for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
//cin >> T;
while (T--) MAIN();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5996kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 5 4 6 8
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 5956kb
input:
10 2 1 Duan 3 2 Duan 4 2 - 5 4 Chang 6 2 Chang 7 1 Duan 8 6 Tong 9 6 Tong 10 3 Chang
output:
YES 3 10 9 8 2 6 7 5
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 6312kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 26ms
memory: 8716kb
input:
100000 2 1 Duan 3 1 Duan 4 3 - 5 4 Duan 6 3 - 7 4 Duan 8 4 - 9 8 - 10 7 Duan 11 9 - 12 7 Duan 13 7 Duan 14 8 Duan 15 13 - 16 10 Duan 17 11 Duan 18 12 - 19 1 Duan 20 5 Duan 21 4 Duan 22 14 Duan 23 16 - 24 22 Duan 25 16 Duan 26 13 - 27 13 - 28 17 - 29 5 Duan 30 22 - 31 23 - 32 9 Duan 33 5 - 34 30 Duan...
output:
YES 56115 46666 38802 88119 10006 93143 76473 31531 15988 42604 30148 6569 2008 11412 46703 64525 70618 71289 47748 81204 20514 42353 46131 97634 82155 83516 62410 66867 9975 15712 3205 4978 5622 83026 10902 48783 30893 82167 65878 93809 66951 33377 66936 94549 64411 79128 22475 8453 36857 54702 905...
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 22ms
memory: 8692kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 4 - 7 6 - 8 7 - 9 5 - 10 9 - 11 10 - 12 6 - 13 12 - 14 11 - 15 9 - 16 14 - 17 16 - 18 10 - 19 15 - 20 13 - 21 20 - 22 17 - 23 22 - 24 22 Duan 25 11 - 26 12 - 27 20 - 28 18 - 29 28 - 30 16 - 31 28 - 32 30 - 33 31 - 34 28 - 35 34 - 36 35 - 37 22 - 38 34 - 39 38 - 40 35...
output:
YES 5203 28541 8106 5981 7551 7900 47998 53424 86909 91669 72002 40295 32334 65376 57528 95652 91216 66693 98194 88445 44959 54118 74202 76761 64661 71470 30271 85084 41192 60344 10342 41421 12876 79425 25933 35989 39297 41959 46303 94979 10581 46189 14956 51797 41806 82599 60566 26090 48923 94132 6...
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 30ms
memory: 9028kb
input:
100000 2 1 - 3 2 - 4 3 Duan 5 4 Chang 6 5 Duan 7 6 Chang 8 7 Duan 9 8 Chang 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 12 Duan 15 14 Chang 16 15 Tong 17 15 Tong 18 17 Duan 19 18 Duan 20 19 Chang 21 18 Duan 22 21 Duan 23 18 Chang 24 21 - 25 24 Duan 26 25 Chang 27 26 Duan 28 27 Chang 29 26 Duan 3...
output:
YES 19 20 55 65 52 53 46 48 35 36 22 34 58 61 56 57 1097 1206 1522 1593 1890 1938 1217 1365 1191 1295 2158 2188 1764 2845 1646 1408 3147 5721 2746 2810 2937 3194 2710 2399 3657 3778 2668 3580 2259 2179 2122 2174 2204 2379 2392 2449 2218 2499 2233 2369 2020 2077 9174 8244 14498 15184 14362 15193 1040...
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 22ms
memory: 8924kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 Duan 11 10 - 12 11 Chang 13 12 Duan 14 13 Chang 15 14 - 16 15 - 17 16 Duan 18 17 Chang 19 17 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 Duan 27 26 - 28 27 Duan 29 28 - 30 29 Chang 31 28 - 32 31 Chang 33 32 - 34 32 - 35 34 - 36 ...
output:
YES 81 85 107 105 117 103 168 172 273 275 321 333 369 384 314 327 433 463 437 429 543 588 667 639 1167 1273 1160 1375 1117 1176 1021 995 926 929 832 1059 1196 1242 1329 1328 1254 1259 1194 1213 1150 1275 1521 1689 1424 1620 1226 1229 1134 1277 915 1099 1218 1237 1316 1358 1284 1350 2462 2524 2128 23...
result:
ok Correct.
Test #8:
score: 0
Accepted
time: 34ms
memory: 9332kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 - 10 9 Chang 11 10 - 12 11 Duan 13 12 Chang 14 13 - 15 14 Duan 16 15 Chang 17 16 - 18 17 - 19 18 Duan 20 19 - 21 20 - 22 21 - 23 22 Chang 24 23 - 25 24 Duan 26 25 - 27 26 Chang 28 27 - 29 28 - 30 29 - 31 30 Duan 32 31 - 33 32 - 34 33 - 35 34 - ...
output:
YES 68 69 118 120 227 237 221 225 266 265 314 323 304 309 343 346 345 352 341 338 347 350 392 401 436 439 469 471 473 474 463 472 480 482 495 499 477 483 567 570 604 613 584 588 576 577 738 744 739 743 730 732 848 851 809 841 881 886 911 930 947 951 1007 1029 964 1002 946 958 914 919 939 942 952 959...
result:
ok Correct.
Test #9:
score: 0
Accepted
time: 33ms
memory: 9568kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 Chang 10 9 - 11 10 Duan 12 11 - 13 12 Chang 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 Duan 19 18 - 20 19 Chang 21 20 Duan 22 21 Chang 23 22 - 24 23 Duan 25 24 Chang 26 25 Duan 27 26 - 28 27 - 29 28 Chang 30 29 Duan 31 30 Chang 32 31 - 33 32 ...
output:
YES 238 239 272 274 343 344 415 416 432 433 477 478 512 515 539 544 579 582 631 633 700 711 717 724 719 730 784 787 780 782 773 772 777 783 831 830 824 821 810 816 849 845 858 860 868 872 897 895 876 894 873 871 929 936 986 999 981 984 976 980 964 966 950 955 958 967 968 977 996 997 993 995 1038 103...
result:
ok Correct.
Test #10:
score: 0
Accepted
time: 19ms
memory: 10632kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 - 11 10 - 12 11 - 13 12 - 14 13 - 15 14 - 16 15 - 17 16 - 18 17 - 19 18 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 - 27 26 - 28 27 - 29 28 - 30 29 - 31 30 - 32 31 - 33 32 - 34 33 - 35 34 - 36 35 - 37 36 - 38 37 - 39 38 - 40 39 ...
output:
YES 4915 4986 6570 6738 13597 14195 22019 22308 31792 31800 38225 38186 43803 43898 41995 41864 42327 42725 43807 43871 43542 43953 46361 46356 47608 47755 46932 47521 44955 46885 48486 48399 49839 50116 49668 49912 53355 54823 54273 54714 53853 54239 52524 52947 55640 57456 58053 58348 59228 59658 ...
result:
ok Correct.
Test #11:
score: 0
Accepted
time: 17ms
memory: 7952kb
input:
100000 2 1 - 3 1 - 4 2 - 5 1 - 6 1 - 7 2 Duan 8 4 - 9 1 - 10 1 - 11 2 - 12 2 - 13 2 - 14 6 - 15 1 - 16 6 - 17 1 - 18 5 - 19 1 - 20 1 - 21 2 - 22 8 - 23 6 - 24 1 - 25 4 Duan 26 1 - 27 10 - 28 1 - 29 8 - 30 5 - 31 7 - 32 2 - 33 3 - 34 12 - 35 3 - 36 1 - 37 12 - 38 8 - 39 8 - 40 1 - 41 4 - 42 16 - 43 8...
output:
YES 34406 34242 23870 14906 79207 28768 68052 50509 32304 70759 36687 70523 68751 36153 3567 47669 70173 18177 58218 50978 56574 27598 6904 46683 47073 79895 4139 85751 17677 83196 90916 65881 67031 44928 25922 49996 95211 28068 69374 43712 19260 84697 70765 32128 79850 30451 12144 92289 51006 99611...
result:
ok Correct.
Test #12:
score: 0
Accepted
time: 18ms
memory: 7628kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 3 - 11 1 - 12 2 - 13 2 - 14 2 - 15 1 - 16 2 - 17 2 - 18 1 - 19 1 - 20 1 - 21 2 - 22 1 - 23 2 - 24 2 - 25 1 - 26 1 - 27 4 - 28 1 - 29 2 - 30 3 - 31 1 - 32 10 - 33 6 - 34 4 - 35 1 - 36 2 Duan 37 1 - 38 4 - 39 10 - 40 1 - 41 1 - 42 3 - 43 6 - 44...
output:
YES 66302 15102 40113 37177 67876 67735 98880 70745 84740 75547 71830 88398 85699 62593 6455 71970 21755 94458 39981 74239 13515 71421 71660 37672 91238 90862 19470 42744 72747 13573 81223 10218 87004 15063 4280 19357 6427 44673 68085 92721 33161 17731 358 45357 65914 49326 93622 45470 15964 91832 3...
result:
ok Correct.
Test #13:
score: 0
Accepted
time: 22ms
memory: 7540kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 - 8 1 Duan 9 1 Duan 10 1 - 11 1 Duan 12 1 - 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 2 - 19 1 Duan 20 1 Duan 21 2 - 22 2 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 2 Duan 28 1 Duan 29 2 Duan 30 1 Duan 31 2 Duan 32 1 - 33 1 Duan...
output:
YES 95158 63894 88086 88697 75216 85544 72642 73765 69085 72241 61983 14063 54430 55203 41588 50491 38849 40110 27596 34955 1136 15274 18595 10786 24025 21493 30164 25178 40282 30800 52476 50699 76452 59910 86389 79238 96792 91441 1197 30463 46043 34098 49151 47433 57549 56601 65754 59254 87547 6698...
result:
ok Correct.
Test #14:
score: 0
Accepted
time: 13ms
memory: 7476kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 - 13 1 Duan 14 1 - 15 1 - 16 1 - 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 - 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 Duan 30 1 - 31 1 - 32 2 Duan 33 1 - 34 1 - 35 1 Duan 36 1 - 37 1 - 38 1 - 39 1 - 40 1 - 41 1 - 42 1 - 43...
output:
YES 62964 51260 73003 64799 98672 87232 38059 31245 58383 47626 82570 78385 91105 84269 90700 67893 97507 95599 96567 51711 2480 84425 97467 90521 3614 97387 20327 52378 31941 24851 35502 34768 37919 36133 41305 38081 47134 46820 18144 51834 53825 52602 63344 60150 68450 65516 84495 79862 90845 8874...
result:
ok Correct.
Test #15:
score: 0
Accepted
time: 12ms
memory: 7448kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 Duan 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 - 13 1 - 14 1 - 15 1 - 16 1 - 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 - 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 - 30 1 - 31 1 - 32 1 - 33 1 Duan 34 1 - 35 1 - 36 1 - 37 1 - 38 1 - 39 1 - 40 1 - 41 1 - 42 1 - 43 1 ...
output:
YES 97806 51853 81679 89831 62015 70717 59449 60751 54934 56321 53261 54125 49313 24271 46496 49018 39709 43803 38753 39458 38484 38738 32530 37384 99744 58304 97190 99690 88437 93135 73977 76662 71317 73029 61172 68370 58424 61007 57761 18859 55259 57280 46485 54712 43694 44356 34688 39921 30675 33...
result:
ok Correct.
Test #16:
score: 0
Accepted
time: 19ms
memory: 7608kb
input:
100000 2 1 Duan 3 1 Duan 4 1 - 5 1 Duan 6 1 - 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 - 12 1 - 13 1 - 14 1 Duan 15 1 Duan 16 1 Duan 17 1 - 18 1 Duan 19 1 Duan 20 1 Duan 21 1 - 22 1 - 23 1 Duan 24 1 Duan 25 1 Duan 26 1 - 27 1 - 28 1 Duan 29 1 Duan 30 1 - 31 1 Duan 32 1 Duan 33 1 - 34 1 Duan 35 1 - ...
output:
YES 336 82705 72014 60220 95022 80211 94029 93125 85950 59250 89854 77242 61755 56243 86382 80147 91748 86818 408 37709 89771 87876 452 83493 481 97158 614 92488 824 95750 31237 30379 31062 31218 30964 31048 30850 30860 30666 30689 30487 30642 30316 31450 30147 30298 29748 29890 29652 29745 29618 29...
result:
ok Correct.
Test #17:
score: 0
Accepted
time: 16ms
memory: 8408kb
input:
100000 2 1 - 3 1 - 4 2 - 5 2 - 6 2 Duan 7 3 - 8 1 - 9 1 - 10 6 - 11 3 - 12 2 - 13 7 - 14 1 - 15 9 - 16 11 - 17 13 - 18 9 - 19 16 - 20 19 - 21 8 - 22 5 - 23 14 - 24 21 - 25 21 - 26 16 - 27 5 - 28 5 - 29 19 - 30 8 - 31 24 - 32 30 - 33 12 Duan 34 9 - 35 12 Duan 36 6 - 37 15 - 38 26 - 39 29 - 40 13 - 41...
output:
NO
result:
ok Correct.
Test #18:
score: 0
Accepted
time: 21ms
memory: 8452kb
input:
100000 2 1 Duan 3 2 Duan 4 3 - 5 3 Duan 6 4 - 7 4 Duan 8 3 Duan 9 2 - 10 4 Duan 11 8 Duan 12 6 - 13 3 Duan 14 6 Duan 15 7 Duan 16 6 Duan 17 14 Tong 18 7 - 19 16 Duan 20 14 Duan 21 12 Duan 22 20 Duan 23 14 Duan 24 19 - 25 2 Duan 26 22 - 27 24 Duan 28 8 Duan 29 4 Duan 30 23 Duan 31 24 Duan 32 23 Duan ...
output:
NO
result:
ok Correct.
Test #19:
score: 0
Accepted
time: 16ms
memory: 8836kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 - 7 4 - 8 7 - 9 8 - 10 9 - 11 10 Duan 12 9 - 13 12 - 14 12 - 15 10 - 16 8 - 17 13 - 18 10 - 19 14 - 20 13 - 21 19 - 22 19 Duan 23 11 - 24 23 Duan 25 23 - 26 5 - 27 22 - 28 22 Duan 29 17 - 30 29 - 31 29 - 32 17 - 33 27 - 34 33 Duan 35 31 - 36 24 - 37 34 - 38 37 - 39...
output:
NO
result:
ok Correct.
Test #20:
score: 0
Accepted
time: 23ms
memory: 9088kb
input:
100000 2 1 Duan 3 2 Chang 4 3 - 5 4 - 6 5 - 7 6 Duan 8 7 - 9 8 Chang 10 9 Duan 11 10 Chang 12 11 - 13 12 Duan 14 13 Chang 15 13 - 16 15 - 17 15 - 18 15 Duan 19 18 - 20 19 Duan 21 19 Chang 22 20 - 23 22 - 24 21 Duan 25 23 - 26 22 - 27 25 Chang 28 26 - 29 28 Duan 30 24 Chang 31 28 - 32 23 - 33 28 - 34...
output:
NO
result:
ok Correct.
Test #21:
score: 0
Accepted
time: 22ms
memory: 8896kb
input:
100000 2 1 Duan 3 2 Chang 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 - 9 8 Chang 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 12 - 15 14 - 16 15 Duan 17 16 Chang 18 17 - 19 17 Duan 20 19 - 21 19 Chang 22 21 - 23 21 Duan 24 23 Duan 25 24 Chang 26 24 Chang 27 24 Duan 28 27 - 29 28 Chang 30 28 Duan 31 30 - 32 3...
output:
NO
result:
ok Correct.
Test #22:
score: 0
Accepted
time: 23ms
memory: 8488kb
input:
100000 2 1 Duan 3 2 Chang 4 3 Duan 5 4 - 6 5 Chang 7 6 - 8 7 Duan 9 8 - 10 9 Chang 11 10 Duan 12 11 Chang 13 12 - 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 Duan 19 18 - 20 19 - 21 20 - 22 21 Chang 23 22 - 24 23 Duan 25 24 Chang 26 25 - 27 26 Duan 28 27 - 29 28 Chang 30 28 Duan 31 30 - 32 31 Chang...
output:
NO
result:
ok Correct.
Test #23:
score: 0
Accepted
time: 19ms
memory: 8912kb
input:
100000 2 1 Duan 3 2 - 4 3 - 5 4 - 6 5 - 7 6 - 8 7 - 9 8 - 10 9 - 11 10 - 12 11 Chang 13 12 Duan 14 13 - 15 14 - 16 15 Chang 17 16 Duan 18 17 Chang 19 18 - 20 19 - 21 20 - 22 21 - 23 22 - 24 23 - 25 24 - 26 25 Duan 27 26 - 28 27 - 29 28 - 30 29 - 31 30 - 32 31 - 33 32 - 34 33 Chang 35 34 - 36 35 - 37...
output:
NO
result:
ok Correct.
Test #24:
score: 0
Accepted
time: 13ms
memory: 10968kb
input:
100000 2 1 - 3 2 - 4 3 - 5 4 - 6 5 Duan 7 6 - 8 7 Chang 9 8 - 10 9 - 11 10 - 12 11 - 13 12 - 14 13 Duan 15 14 - 16 15 Chang 17 16 - 18 17 - 19 18 - 20 19 Duan 21 20 - 22 21 - 23 22 - 24 23 Chang 25 24 - 26 25 Duan 27 26 Chang 28 27 Duan 29 28 - 30 29 - 31 30 - 32 31 Chang 33 32 Duan 34 33 - 35 34 - ...
output:
NO
result:
ok Correct.
Test #25:
score: 0
Accepted
time: 23ms
memory: 7912kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 - 6 3 - 7 2 - 8 2 - 9 4 - 10 1 - 11 2 - 12 3 Duan 13 2 - 14 4 - 15 3 - 16 3 - 17 2 - 18 2 - 19 1 - 20 7 Duan 21 1 - 22 15 - 23 6 - 24 1 - 25 8 - 26 11 - 27 5 - 28 16 - 29 17 - 30 16 - 31 3 - 32 7 - 33 3 Duan 34 7 Duan 35 3 - 36 8 - 37 6 - 38 16 - 39 3 - 40 3 - 41 11 -...
output:
NO
result:
ok Correct.
Test #26:
score: 0
Accepted
time: 22ms
memory: 7724kb
input:
100000 2 1 - 3 1 - 4 1 - 5 1 - 6 1 - 7 1 Duan 8 1 - 9 1 - 10 1 - 11 3 - 12 2 - 13 1 - 14 1 - 15 1 - 16 2 - 17 1 Duan 18 3 - 19 1 - 20 1 Duan 21 8 - 22 2 - 23 3 - 24 3 Duan 25 1 - 26 1 - 27 1 - 28 1 - 29 4 - 30 1 - 31 3 - 32 3 - 33 3 - 34 2 - 35 1 - 36 1 Duan 37 1 - 38 3 - 39 2 - 40 4 - 41 2 Duan 42 ...
output:
NO
result:
ok Correct.
Test #27:
score: 0
Accepted
time: 18ms
memory: 7552kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 Duan 12 1 Duan 13 1 Duan 14 2 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 2 Duan 19 1 Duan 20 1 - 21 1 Duan 22 1 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 2 Duan 28 1 Duan 29 1 Duan 30 1 - 31 1 Duan 32 1 Du...
output:
NO
result:
ok Correct.
Test #28:
score: 0
Accepted
time: 15ms
memory: 7364kb
input:
100000 2 1 - 3 1 Duan 4 1 - 5 1 - 6 1 - 7 1 Duan 8 1 - 9 1 Duan 10 1 - 11 1 Duan 12 1 Duan 13 1 Duan 14 1 Duan 15 1 Duan 16 1 - 17 1 Duan 18 1 Duan 19 1 Duan 20 1 Duan 21 1 - 22 1 - 23 1 Duan 24 1 - 25 1 Duan 26 1 Duan 27 1 Duan 28 1 Duan 29 1 Duan 30 1 Duan 31 1 Duan 32 1 - 33 1 - 34 1 Duan 35 1 Du...
output:
NO
result:
ok Correct.
Test #29:
score: 0
Accepted
time: 15ms
memory: 7616kb
input:
100000 2 1 Duan 3 1 Duan 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 - 9 1 Duan 10 1 Duan 11 1 Duan 12 1 - 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 1 Duan 19 1 Duan 20 1 - 21 1 - 22 1 Duan 23 1 - 24 1 Duan 25 1 Duan 26 1 Duan 27 1 Duan 28 1 Duan 29 1 Duan 30 1 Duan 31 1 Duan 32 1 Duan 33 1 -...
output:
NO
result:
ok Correct.
Test #30:
score: 0
Accepted
time: 16ms
memory: 7600kb
input:
100000 2 1 Duan 3 1 - 4 1 Duan 5 1 Duan 6 1 Duan 7 1 Duan 8 1 Duan 9 1 Duan 10 1 Duan 11 1 Duan 12 1 Duan 13 1 Duan 14 1 Duan 15 1 Duan 16 1 Duan 17 1 Duan 18 1 Duan 19 1 - 20 1 Duan 21 1 Duan 22 1 Duan 23 1 Duan 24 1 Duan 25 1 Duan 26 1 Duan 27 1 Duan 28 1 - 29 1 Duan 30 1 Duan 31 1 Duan 32 1 - 33 ...
output:
NO
result:
ok Correct.
Test #31:
score: 0
Accepted
time: 20ms
memory: 41764kb
input:
100000 2 1 Duan 3 2 - 4 3 Chang 5 4 - 6 5 Duan 7 6 Chang 8 7 - 9 8 - 10 9 Duan 11 10 Chang 12 11 Duan 13 12 Chang 14 13 Duan 15 14 Chang 16 15 - 17 16 - 18 17 - 19 18 Duan 20 19 - 21 20 - 22 21 Chang 23 22 Duan 24 23 Chang 25 24 - 26 25 Duan 27 26 Chang 28 27 Duan 29 28 - 30 29 Chang 31 30 Duan 32 3...
output:
YES 27101 27102 29449 29450 30581 30582 31108 31109 33544 33545 34348 34349 35394 35395 35626 35627 35741 35742 36325 36326 36979 36980 37025 37026 37780 37781 37916 37917 38565 38566 38778 38779 38882 38884 39162 39163 39440 39441 39609 39610 39688 39689 39923 39924 39994 39995 40980 40981 41017 41...
result:
ok Correct.
Test #32:
score: 0
Accepted
time: 11ms
memory: 7200kb
input:
100000 2 1 Duan 3 1 - 4 1 - 5 1 - 6 1 - 7 1 - 8 1 - 9 1 - 10 1 - 11 1 - 12 1 Tong 13 1 - 14 1 - 15 1 - 16 1 Tong 17 1 - 18 1 - 19 1 - 20 1 - 21 1 - 22 1 Tong 23 1 - 24 1 - 25 1 - 26 1 - 27 1 - 28 1 - 29 1 - 30 1 - 31 1 - 32 1 - 33 1 - 34 1 - 35 1 - 36 1 - 37 1 - 38 1 Tong 39 1 - 40 1 - 41 1 - 42 1 -...
output:
YES 84085 83748 84039 84052 84021 84036 83963 83989 83892 83894 83862 83875 83778 83794 83732 84100 83697 83710 83646 83679 83589 83641 83505 83567 83382 83453 83339 83381 84988 84510 84948 84986 84880 84886 84830 84874 84706 84731 84652 84680 84567 84592 84494 83330 84459 84484 84340 84457 84310 84...
result:
ok Correct.
Test #33:
score: 0
Accepted
time: 25ms
memory: 8564kb
input:
93284 2 1 - 3 1 Duan 4 2 - 5 4 - 6 2 - 7 4 Duan 8 1 - 9 4 - 10 4 Duan 11 6 - 12 7 - 13 6 - 14 1 Duan 15 4 - 16 9 - 17 12 - 18 15 - 19 6 Duan 20 1 - 21 15 - 22 2 - 23 5 Duan 24 7 - 25 22 - 26 13 - 27 12 - 28 6 - 29 27 Duan 30 7 Duan 31 9 - 32 14 - 33 3 - 34 21 - 35 18 - 36 35 - 37 7 - 38 17 Duan 39 2...
output:
YES 9427 44871 75107 58881 7193 33984 9737 33178 31043 89725 50618 31602 870 88133 52086 58845 21758 63567 16605 85296 28152 44633 2705 65095 18041 90927 56227 42717 10288 88253 16710 61450 49645 71661 30561 48970 20860 37354 31734 34821 29953 37862 37189 80450 56610 93257 30431 14996 42455 91146 34...
result:
ok Correct.
Test #34:
score: 0
Accepted
time: 29ms
memory: 8368kb
input:
92284 2 1 Duan 3 2 - 4 3 Duan 5 2 Duan 6 3 - 7 4 Duan 8 6 Duan 9 4 Duan 10 6 Duan 11 4 Duan 12 8 Chang 13 1 Duan 14 5 Duan 15 5 - 16 15 Duan 17 15 Duan 18 13 Chang 19 12 Duan 20 4 - 21 1 Duan 22 17 Duan 23 2 Duan 24 14 Duan 25 17 Duan 26 22 Duan 27 4 - 28 26 Duan 29 9 Duan 30 15 Duan 31 3 Duan 32 7 ...
output:
YES 17459 51080 16873 32219 11101 56156 52633 74549 51694 82117 38566 32559 186 48460 25888 41891 83294 84667 52019 87183 77715 88982 13583 78351 83209 87627 62069 46901 8557 86376 986 3604 79770 83765 49864 80461 22996 74127 42259 69795 91303 61472 29187 35154 25303 15829 62442 27245 171 52319 3885...
result:
ok Correct.
Test #35:
score: 0
Accepted
time: 30ms
memory: 8332kb
input:
93444 2 1 - 3 1 Duan 4 1 Duan 5 2 - 6 4 - 7 3 - 8 6 Duan 9 6 Duan 10 9 - 11 2 - 12 1 - 13 11 - 14 5 - 15 14 Duan 16 11 - 17 16 - 18 4 - 19 7 Duan 20 15 - 21 17 - 22 21 - 23 20 - 24 23 Duan 25 7 - 26 14 Duan 27 18 - 28 13 Duan 29 2 Duan 30 19 Duan 31 5 - 32 7 Duan 33 23 Duan 34 17 Duan 35 2 Duan 36 2...
output:
YES 54500 63791 4643 49024 55459 37302 26344 33770 28229 81449 65404 87768 33539 24623 51327 82147 90272 70787 9603 14888 47877 47285 29487 40135 353 4308 34651 72113 41429 58261 22648 64780 81320 68254 50381 57783 25357 85526 43913 76795 41202 34185 46835 41133 140 54622 10796 76020 47575 1923 1383...
result:
ok Correct.
Test #36:
score: 0
Accepted
time: 25ms
memory: 8452kb
input:
98244 2 1 Duan 3 1 Duan 4 3 Duan 5 4 Duan 6 4 Duan 7 4 Duan 8 5 Duan 9 8 Duan 10 5 Duan 11 9 Duan 12 3 Duan 13 11 Tong 14 5 Duan 15 5 Duan 16 12 Duan 17 2 Duan 18 3 Duan 19 4 Duan 20 2 Duan 21 6 Duan 22 21 Duan 23 1 - 24 15 - 25 20 Duan 26 8 Duan 27 13 Duan 28 12 Duan 29 22 Duan 30 24 Duan 31 21 Dua...
output:
YES 16406 33409 30277 15284 6139 35906 93724 58902 18729 47922 20659 24670 41216 47533 48839 84590 4161 87728 74471 95897 3459 23810 9591 29076 34342 9185 95194 80103 22109 87229 14850 28966 8235 15423 13261 42356 9379 78438 35400 89672 33413 67130 9648 91476 23306 73800 877 79990 3540 87242 92296 9...
result:
ok Correct.
Test #37:
score: 0
Accepted
time: 8ms
memory: 6692kb
input:
25284 2 1 Duan 3 2 - 4 3 - 5 3 Duan 6 2 Duan 7 3 Duan 8 1 Duan 9 5 - 10 4 - 11 5 Duan 12 4 Duan 13 1 Duan 14 4 - 15 10 Duan 16 8 - 17 13 - 18 15 - 19 12 - 20 16 Duan 21 6 Duan 22 2 Duan 23 19 - 24 12 - 25 2 - 26 19 Duan 27 5 - 28 4 - 29 9 - 30 12 Duan 31 7 Duan 32 31 - 33 21 - 34 24 Duan 35 28 Duan ...
output:
YES 5340 14929 7415 15736 22917 23406 15197 14380 14590 24417 7880 3602 15884 1894 12672 9136 3206 5678 15621 24111 20232 14368 25101 21718 1931 7241 19471 24489 8812 23289 12521 22451 130 1629 21864 23008 3189 9095 15113 22734 10604 12465 6641 6996 1537 22852 765 23329 16208 20447 2439 18299 9351 1...
result:
ok Correct.
Test #38:
score: 0
Accepted
time: 23ms
memory: 8348kb
input:
93246 2 1 Duan 3 2 Duan 4 3 Duan 5 1 - 6 4 Tong 7 4 Duan 8 4 Duan 9 8 - 10 6 Duan 11 2 Duan 12 1 Duan 13 11 Duan 14 8 Duan 15 1 Duan 16 8 Duan 17 10 Duan 18 3 Duan 19 1 Duan 20 18 Duan 21 10 Duan 22 14 Duan 23 11 Duan 24 19 Duan 25 21 Duan 26 17 Duan 27 24 Duan 28 24 Duan 29 17 Tong 30 23 Duan 31 17...
output:
YES 20027 82440 37790 82065 13555 55902 9444 93214 14967 54322 8102 47686 23936 71322 77717 78461 45254 48337 52000 83570 24317 29015 723 91719 35283 63413 89556 3250 81387 60951 76768 50544 6264 24023 27168 92751 65278 78391 14547 46265 81407 92070 47136 69857 17204 28099 19861 33721 24774 55462 33...
result:
ok Correct.
Test #39:
score: 0
Accepted
time: 29ms
memory: 8436kb
input:
99837 2 1 - 3 1 - 4 3 Duan 5 2 Duan 6 5 Duan 7 3 Duan 8 5 - 9 6 Duan 10 4 - 11 4 - 12 6 Duan 13 8 - 14 7 - 15 10 Duan 16 11 Duan 17 8 Duan 18 6 - 19 13 Duan 20 16 Duan 21 20 - 22 19 Chang 23 4 Duan 24 13 Duan 25 21 - 26 17 Duan 27 7 Duan 28 8 - 29 3 - 30 18 - 31 21 Duan 32 27 Duan 33 21 Duan 34 17 -...
output:
YES 77117 37610 19111 30206 88367 70345 20744 36504 43637 75785 14266 79180 26231 83709 85507 55639 3564 10520 11286 21314 30850 90540 51043 56410 66938 77737 86756 89082 10348 37423 10238 81449 63757 89645 30451 42718 49790 91346 27842 74087 61765 86402 33536 73518 45163 55707 25335 33231 76696 513...
result:
ok Correct.
Test #40:
score: 0
Accepted
time: 26ms
memory: 8336kb
input:
91248 2 1 Duan 3 1 Duan 4 1 Duan 5 2 Duan 6 3 Duan 7 3 Chang 8 2 Duan 9 1 Duan 10 7 Duan 11 10 Duan 12 4 Duan 13 2 Duan 14 11 Duan 15 6 Duan 16 8 Duan 17 7 Duan 18 2 Duan 19 15 Duan 20 4 Duan 21 7 Duan 22 6 Duan 23 6 Duan 24 20 Duan 25 13 Duan 26 22 Duan 27 5 Duan 28 19 Duan 29 14 Duan 30 12 - 31 8 ...
output:
YES 91137 22567 6625 32840 2746 72793 58707 49857 6406 9195 17873 75118 13271 70816 35070 36187 34727 36004 60624 77775 40146 56136 3419 7879 81884 50744 75987 35818 56940 90945 1090 12926 73408 77013 45541 48058 55452 26944 55908 58680 43609 78364 45709 77661 32151 55964 12836 71423 21580 52096 122...
result:
ok Correct.
Test #41:
score: 0
Accepted
time: 26ms
memory: 8312kb
input:
93538 2 1 - 3 2 - 4 2 - 5 3 Duan 6 4 - 7 4 - 8 2 - 9 1 - 10 7 - 11 4 Duan 12 8 - 13 9 - 14 1 Duan 15 7 Duan 16 3 - 17 5 - 18 14 Duan 19 5 - 20 7 - 21 15 Duan 22 9 - 23 8 - 24 16 Duan 25 5 Duan 26 6 Duan 27 10 - 28 7 - 29 21 Duan 30 1 - 31 18 - 32 13 - 33 6 - 34 28 - 35 16 Duan 36 32 Duan 37 22 - 38 ...
output:
YES 19363 43838 63190 42715 10322 20329 78903 70798 14986 45972 83054 62809 1456 52182 19710 62218 84523 85461 12256 52940 7475 31914 86366 39273 21575 61296 12897 78432 23096 67416 61831 81263 686 53716 24734 31961 29776 45084 57302 70937 58268 25231 35275 85989 19412 19663 45326 70970 34007 55647 ...
result:
ok Correct.
Test #42:
score: 0
Accepted
time: 28ms
memory: 8504kb
input:
92384 2 1 Duan 3 2 - 4 3 Duan 5 3 Duan 6 3 - 7 2 Duan 8 1 - 9 7 Duan 10 5 Chang 11 4 - 12 3 Duan 13 7 - 14 9 Duan 15 14 Chang 16 3 Duan 17 6 Duan 18 10 Duan 19 17 Duan 20 10 - 21 2 Duan 22 10 - 23 5 Duan 24 18 - 25 11 - 26 13 Duan 27 12 Duan 28 1 - 29 18 Duan 30 28 Duan 31 28 - 32 16 - 33 27 Duan 34...
output:
YES 40096 40387 43478 83783 3661 3917 89303 50150 15374 18917 48940 34799 61144 81225 81589 63107 20682 29948 1795 14730 13591 23638 2983 84669 33792 38473 26822 33668 72727 91365 52159 58495 10991 54079 73581 69625 43086 31305 39523 48339 14352 88518 65295 91546 34909 89085 3467 34637 17285 74155 9...
result:
ok Correct.
Test #43:
score: 0
Accepted
time: 0ms
memory: 6604kb
input:
1
output:
YES
result:
ok Correct.