QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561887 | #5423. Perfect Matching | louhao088# | WA | 404ms | 26300kb | C++23 | 2.8kb | 2024-09-13 12:03:12 | 2024-09-13 12:03:12 |
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)
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: 12072kb
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: 404ms
memory: 26300kb
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:
No No No Yes 99993 99992 99982 99980 99977 99979 99966 99967 99887 99888 99867 99868 99840 99841 99807 99808 99792 99793 99716 99717 99689 99690 99674 99675 99653 99654 99642 99643 99582 99583 99572 99573 99563 99565 99548 99550 99534 99535 99518 99519 99515 99516 99506 99507 99458 99460 99429 99430...
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)