QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662123 | #5423. Perfect Matching | Andycraft | WA | 197ms | 22284kb | C++20 | 2.0kb | 2024-10-20 21:13:42 | 2024-10-20 21:13:42 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
template <class T> using Arr = std::vector<T>;
struct edge_t {
int to, id;
};
const int MAXN = 100002;
int n, a[MAXN];
Arr<edge_t> e[MAXN * 2], tr[MAXN * 2];
int vis[MAXN * 2], fa[MAXN * 2], sz[MAXN * 2], out[MAXN * 2];
void add(int u, int v, int w) {
// printf("add %d %d %d\n", u, v, w);
e[u].push_back({v, w});
e[v].push_back({u, w});
}
Arr<std::pair<int, int>> ans;
void connect(int u, int v) {
ans.push_back({u, v});
}
void dfs(int p) {
sz[p] = 1, vis[p] = true;
for (auto [to, _] : e[p])
if (to != fa[p] && !vis[to]) {
fa[to] = p;
tr[p].push_back({to, _});
dfs(to);
sz[p] += sz[to];
}
int tmp = 0, last;
for (auto [to, id] : tr[p]) {
if (sz[to] & 1) {
++tmp;
if (tmp & 1)
last = id;
else
connect(id, last);
} else
connect(id, out[to]);
}
if (tmp & 1)
out[p] = last;
assert((tmp & 1) != (sz[p] & 1));
}
void Solve() {
std::cin >> n;
Arr<int> ls, rs;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
ls.push_back(i - a[i]);
rs.push_back(i + a[i]);
}
std::sort(ls.begin(), ls.end());
ls.erase(std::unique(ls.begin(), ls.end()), ls.end());
std::sort(rs.begin(), rs.end());
rs.erase(std::unique(rs.begin(), rs.end()), rs.end());
int ln = (int)ls.size(), rn = (int)rs.size();
auto find = [](Arr<int> &v, int x) { return (int)(std::lower_bound(v.begin(), v.end(), x) - v.begin()); };
for (int i = 0; i < ln + rn; ++i) {
e[i].clear(), tr[i].clear();
vis[i] = false;
fa[i] = -1;
sz[i] = 0;
out[i] = -1;
}
for (int i = 1; i <= n; ++i) {
int l = find(ls, i - a[i]);
int r = find(rs, i + a[i]);
add(l, ln + r, i);
}
ans.clear();
for (int i = 0; i < ln + rn; ++i)
if (!vis[i]) {
dfs(i);
if (~sz[i] & 1)
return puts("No"), void();
}
// assert(ans.size() == n / 2);
puts("Yes");
for (auto [u, v] : ans)
printf("%d %d\n", u, v);
}
int main() {
std::ios::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: 1ms
memory: 5844kb
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 1 4 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 197ms
memory: 22284kb
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 139 79 244 202 310 289 322 316 382 337 451 397 463 460 517 481 526 520 568 556 661 619 763 736 853 790 934 904 988 979 1105 1090 1219 1162 1285 1273 1405 1294 1456 1411 1531 1459 1561 1555 1615 1588 1630 1618 1669 1651 1723 1684 1915 1738 2026 1972 2092 2029 2197 2155 2305 2290 2353 2350 2431 24...
result:
wrong output format Expected integer, but "Yes" found (test case 1)