QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#150142 | #5423. Perfect Matching | rgnerdplayer | AC ✓ | 538ms | 17952kb | C++20 | 2.6kb | 2023-08-25 15:22:11 | 2023-08-25 15:22:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <typename T, class F = less<T>>
struct Discrete {
vector<T> a;
Discrete(const vector<T> &v) : a(v) {
sort(a.begin(), a.end(), F());
a.erase(unique(a.begin(), a.end()), a.end());
}
int size() { return a.size(); }
int operator()(T x) { return lower_bound(a.begin(), a.end(), x, F()) - a.begin(); }
T operator[](int i) { return a[i]; }
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
auto solve = [&]() {
int n;
cin >> n;
vector<int> a(n), x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
x[i] = i - a[i];
y[i] = i + a[i];
}
Discrete dx(x), dy(y);
vector<vector<pair<int, int>>> g(2 * n);
for (int i = 0; i < n; i++) {
x[i] = dx(x[i]), y[i] = dy(y[i]);
g[x[i]].emplace_back(y[i] + n, i);
g[y[i] + n].emplace_back(x[i], i);
}
vector<int> vis(2 * n), dep(2 * n);
vector<pair<int, int>> ans;
auto dfs = [&](auto dfs, int u, int pv, int pe) -> int {
dep[u] = pv == -1 ? 0 : dep[pv] + 1;
vis[u] = true;
vector<int> e;
for (auto [v, i] : g[u]) {
if (v == pv) {
continue;
}
if (vis[v] && dep[v] < dep[u]) {
e.push_back(i);
}
if (!vis[v] && dfs(dfs, v, u, i)) {
e.push_back(i);
}
}
while (int(e.size()) >= 2) {
ans.emplace_back(e.back(), e.end()[-2]);
e.pop_back();
e.pop_back();
}
if (!e.empty() && pe != -1) {
ans.emplace_back(e[0], pe);
return false;
} else {
return true;
}
};
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(dfs, i, -1, -1);
}
}
if (int(ans.size()) != n / 2) {
cout << "No\n";
} else {
cout << "Yes\n";
for (auto [x, y] : ans) {
cout << x + 1 << ' ' << y + 1 << '\n';
}
}
};
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3800kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 6 3 5 2 4 1 Yes 3 1 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 296ms
memory: 16268kb
input:
10 100000 0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...
output:
Yes 21 22 78 77 138 137 201 200 242 244 287 289 309 308 315 314 321 320 335 337 380 382 396 395 450 449 459 458 462 461 480 479 515 517 518 520 524 526 554 556 567 566 617 619 660 659 734 736 761 763 788 790 851 853 903 902 933 932 978 977 987 986 1089 1088 1104 1103 1160 1162 1218 1217 1271 1273 12...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 74 73 72 71 70 69 8 7 6 5 4 3 2 1 38 37 36 35 68 67 66 65 64 63 62 61 60 59 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 34 33 32 31 30 29 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 249ms
memory: 17264kb
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...
output:
Yes 49560 49559 29398 29397 29396 29395 29394 29393 29392 29391 29390 29389 29388 29387 29386 29385 29384 29383 29382 29381 29380 29379 29378 29377 29376 29375 29374 29373 29372 29371 29370 29369 29368 29367 29366 29365 29364 29363 29362 29361 29360 29359 29358 29357 29356 29355 29354 29353 34124 34...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 538ms
memory: 17952kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 89504 28 63463 26518 8564 1121 36811 36817 95315 8931 96991 61541 81303 70110 16772 13611 34736 778 88310 80993 74032 11544 821 940 80608 33052 9050 10585 78597 37367 84943 65442 41232 50244 91157 52881 10333 5417 18933 19162 97729 87006 59542 3408 79681 23980 67617 66364 27149 10211 57643 44140...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 196ms
memory: 3940kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 14 15 57 59 66 67 77 78 98 99 130 129 142 144 161 162 165 167 183 185 184 186 198 199 200 202 205 207 214 215 232 233 243 245 271 270 279 280 284 286 307 308 312 314 315 316 320 321 328 330 333 332 370 372 384 385 387 388 412 413 422 421 424 426 427 428 432 433 435 436 440 442 ...
result:
ok 1000 Cases (1000 test cases)