QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267733 | #5423. Perfect Matching | jrjyy# | AC ✓ | 1029ms | 30044kb | C++20 | 2.1kb | 2023-11-27 17:33:29 | 2023-11-27 17:33:30 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
int cnt = n;
std::vector<std::vector<int>> adj(n);
std::map<int, int> mp;
for (int i = 0; i < n; ++i) {
int x = a[i] + i;
if (!mp.count(x)) {
mp[x] = cnt++;
adj.emplace_back();
}
adj[i].push_back(mp[x]);
adj[mp[x]].push_back(i);
}
mp.clear();
for (int i = 0; i < n; ++i) {
int x = a[i] - i;
if (!mp.count(x)) {
mp[x] = cnt++;
adj.emplace_back();
}
adj[i].push_back(mp[x]);
adj[mp[x]].push_back(i);
}
std::vector<bool> vis(cnt), ok(cnt);
std::vector<int> f(cnt, -1);
std::vector<std::pair<int, int>> ans;
auto dfs = [&](auto self, int u, int fa) -> void {
vis[u] = true;
for (auto v : adj[u]) {
if (v == fa || vis[v]) {
continue;
}
self(self, v, u);
if (v < n && !ok[v]) {
if (f[u] == -1) {
f[u] = v;
} else {
ok[f[u]] = ok[v] = true;
ans.emplace_back(f[u], v);
f[u] = -1;
}
} else if (f[v] != -1) {
ok[f[v]] = ok[u] = true;
ans.emplace_back(f[v], u);
f[v] = -1;
}
}
};
for (int i = n; i < cnt; ++i) {
if (!vis[i]) {
dfs(dfs, i, -1);
if (f[i] != -1) {
std::cout << "No\n";
return;
}
}
}
if (int(ans.size()) * 2 < n) {
std::cout << "No\n";
return;
}
std::cout << "Yes\n";
for (auto [u, v] : ans) {
std::cout << u + 1 << " " << v + 1 << "\n";
}
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 5 2 6 3 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 426ms
memory: 18684kb
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 14 15 16 20 77 78 3 79 137 138 200 201 139 202 242 244 287 289 308 309 314 315 310 316 320 321 335 337 380 382 395 396 322 397 449 450 458 459 451 460 461 462 479 480 463 481 515 517 518 520 524 526 554 556 566 567 617 619 659 660 568 661 734 736 761 763 788 790 851 853 902 903 932 933 904 934 9...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3572kb
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 2 3 4 5 6 7 8 1 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 37 38 35 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 39 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 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 477ms
memory: 30044kb
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 42 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 10...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 1029ms
memory: 21728kb
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 47 48 13 14 89504 28 49 54 57 58 8564 26518 63463 1121 153 222 36811 36817 84 129 8931 95315 506 7625 536 1600 96991 61541 126 132 14495 23105 33602 36346 99 152 107 243 81132 92548 8961 29263 41302 83637 11086 16914 62 7528 859 1003 92 127 513 768 66 118 288 2392 34736 778 12537 4360 542 664 99...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 282ms
memory: 3840kb
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 4 11 6 9 16 17 18 21 23 22 25 27 31 32 34 33 35 42 48 47 51 62 73 72 64 79 82 86 90 96 101 103 108 107 109 111 128 127 121 145 148 147 156 155 157 159 164 166 169 174 180 179 176 191 193 192 195 201 211 210 204 223 229 230 237 244 246 252 261 260 263 262 269 276 282 292 293 294...
result:
ok 1000 Cases (1000 test cases)