QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771631 | #5423. Perfect Matching | chenlinxuan0226 | WA | 459ms | 24920kb | C++14 | 3.2kb | 2024-11-22 14:43:28 | 2024-11-22 14:43:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int T, n, a[100001], fa[100001], siz[100001], cnte, w[100001], v[100001], com[100001], q[100001],
Left[100001];
map<int, vector<int>> s1, s2;
vector<int> Map[100001];
struct edge {
int u, v, c;
} e[400001];
int find(int i) { return fa[i] = (i == fa[i]) ? i : find(fa[i]); }
void clear() {
for (int i = 1; i <= n; i++) v[i] = 0, com[i] = 0;
}
void bfs(int s, int t) {
int ta = 0;
q[ta++] = s;
v[s] = 1;
int h = 0;
while (h < ta) {
int u = q[h++];
for (int& e_ : Map[u]) {
auto& [x, y, c] = e[e_];
if (v[y])
continue;
v[y] = 1, com[y] = e_;
if (y == t) {
int now = y;
while (now != s) e[com[now]].c ^= 1, e[com[now] ^ 1].c ^= 1, now = e[com[now]].u;
return;
}
q[ta++] = y;
}
}
}
void merge(int x, int y) {
++cnte;
e[cnte << 1] = { x, y, 0 };
e[cnte << 1 | 1] = { y, x, 0 };
Map[x].push_back(cnte << 1);
Map[y].push_back(cnte << 1 | 1);
if (find(x) == find(y))
return;
if ((siz[fa[x]] & 1) && (siz[fa[y]] & 1)) {
int nowx = w[fa[x]], nowy = w[fa[y]];
while (nowx && nowx != x)
e[Left[nowx] << 1].c ^= 1, e[Left[nowx] << 1 | 1].c ^= 1, nowx = e[Left[nowx] << 1].u;
while (nowy && nowy != y)
e[Left[nowy] << 1].c ^= 1, e[Left[nowy] << 1 | 1].c ^= 1, nowy = e[Left[nowy] << 1].u;
e[cnte << 1].c ^= 1;
e[cnte << 1 | 1].c ^= 1;
// clear(),bfs(w[fa[x]],w[fa[y]]);
w[fa[y]] = w[fa[x]] = 0;
}
w[fa[y]] = w[fa[x]] | w[fa[y]];
w[fa[x]] = 0;
siz[fa[y]] += siz[fa[x]], siz[fa[x]] = 0, fa[fa[x]] = fa[y];
}
void onlymerge(int x, int y) {
if (find(x) == find(y))
return;
siz[fa[y]] += siz[fa[x]], siz[fa[x]] = 0, fa[fa[x]] = fa[y];
}
int main() {
// ios::sync_with_stdio(false),cin.tie(0);
cin >> T;
while (T--) {
cin >> n;
cnte = 0;
s1.clear();
s2.clear();
for (int i = 1; i <= n; i++)
cin >> a[i], s1[a[i] - i].push_back(i), fa[i] = i, siz[i] = 1, Map[i].clear(), w[i] = i,
Left[i] = 0;
for (int i = 1; i <= n; i++) s2[a[i] - (n - i + 1)].push_back(i);
for (auto& [x, y] : s1)
for (int i = 1; i < y.size(); i++) onlymerge(y[i - 1], y[i]);
for (auto& [x, y] : s2)
for (int i = 1; i < y.size(); i++) onlymerge(y[i - 1], y[i]);
int o = 1;
for (int i = 1; i <= n; i++) o &= !(siz[i] & 1);
if (!o) {
cout << "No\n";
continue;
}
for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
for (auto& [x, y] : s1)
for (int i = 1; i < y.size(); i++) Left[y[i]] = cnte, merge(y[i - 1], y[i]);
for (auto& [x, y] : s2)
for (int i = 1; i < y.size(); i++) merge(y[i - 1], y[i]);
cout << "Yes\n";
for (int i = 1; i <= cnte; i++)
if (e[i << 1].c)
cout << e[i << 1].u << " " << e[i << 1].v << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7840kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 2 5 3 6 1 4 Yes 2 4 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 459ms
memory: 24920kb
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 99986 99988 99974 99976 99968 99970 99965 99966 99962 99963 99959 99960 99957 99958 99954 99955 99947 99949 99945 99946 99933 99934 99917 99919 99912 99913 99902 99904 99878 99880 99875 99876 99854 99855 99836 99837 99833 99835 99825 99826 99819 99820 99800 99802 99767 99768 99744 99745 99737 99...
result:
wrong answer 797 appears more than once (test case 1)