QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561902 | #5423. Perfect Matching | louhao088# | WA | 391ms | 25192kb | C++23 | 2.9kb | 2024-09-13 12:37:35 | 2024-09-13 12:37:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int re, zf; char C;
int read() {
re = 0; zf = 1;
C = getchar();
while (C < '0' || C > '9') {
if (C == '-') zf = -zf;
C = getchar();
}
while (C >= '0' && C <= '9') {
re = re * 10 + C - '0';
C = getchar();
}
return re * zf;
}
const int N = 3e5 + 100;
int n, a[N], b[N], c[N];
int bb[N], cc[N], du[N];
struct node {
int x, to, nxt;
}e[N];
int le[N], KK;
void add(int x, int y, int i) {
e[++KK] = (node){i, y, le[x]}; le[x] = KK;
e[++KK] = (node){i, x, le[y]}; le[y] = KK;
}
vector <int> ans[N];
queue <int> q;
set <int> line;
bool in[N];
void del(int i) {
in[i] = 1; line.erase(i);
int l = b[i], r = c[i];
if (du[r] == 1) swap(l, r);
if (du[l] != 1 && (rand() & 1)) swap(l, r);
if (ans[l].size() & 1) ans[l].push_back(i);
else ans[r].push_back(i);
du[l]--; du[r]--;
if (du[l] == 1) q.push(l);
if (du[r] == 1) q.push(r);
}
void slove() {
srand(time(0));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i] - i; c[i] = a[i] + i;
bb[i] = b[i]; cc[i] = c[i];
}
sort(bb + 1, bb + n + 1); sort(cc + 1, cc + n + 1);
int bn = unique(bb + 1, bb + n + 1) - bb - 1, cn = unique(cc + 1, cc + n + 1) - cc - 1;
for (int i = 1; i <= n; i++) {
b[i] = lower_bound(bb + 1, bb + bn + 1, b[i]) - bb;
}
for (int i = 1; i <= n; i++) {
c[i] = lower_bound(cc + 1, cc + cn + 1, c[i]) - cc + bn;
}
for (int i = 1; i <= n; i++) du[b[i]]++, du[c[i]]++, add(b[i], c[i], i), line.insert(i);
for (int i = 1; i <= n; i++) in[i] = 0;
for (int i = 1; i <= bn + cn; i++)
if (du[i] == 1) q.push(i);
int num = 0;
while (num < n) {
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = le[now]; i; i = e[i].nxt)
if (!in[e[i].x]) {
del(e[i].x); num++;
}
}
if (num < n) {
del(*line.begin()); num++;
}
}
bool yes = 1;
for (int i = 1; i <= bn + cn; i++) {
if (ans[i].size() & 1) {
yes = 0; break;
}
}
if (yes) {
printf("Yes\n");
for (int i = 1; i <= bn + cn; i++) {
for (int j = 0; j + 1 < ans[i].size(); j += 2) {
if (abs(ans[i][j] - ans[i][j + 1]) != abs(a[ans[i][j]] - a[ans[i][j + 1]])) while (1);
printf("%d %d\n", ans[i][j], ans[i][j + 1]);
}
}
}
else {
printf("No\n");
}
line.clear();
while (!q.empty()) q.pop();
for (int i = 1; i <= bn + cn; i++) du[i] = 0, ans[i].clear();
for (int i = 1; i <= n; i++) in[i] = 0;
for (int i = 1; i <= bn + cn; i++) le[i] = 0; KK = 0;
}
int main()
{
int t = read();
while (t--) slove();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12160kb
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 4 1 Yes 2 4 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 391ms
memory: 25192kb
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 99966 99965 99962 99963 99947 99949 99933 99934 99921 99922 99919 99917 99914 99916 99896 99897 99878 99880 99836 99837 99804 99805 99800 99802 99773 99775 99740 99741 99690 99691 99657 99658 99641 99642 99629 99630 99608 99610 99578 99579 99572 99573 99557 99...
result:
wrong answer std outputs a valid answer while participant doesn't (test case 2)