QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#561860 | #5423. Perfect Matching | louhao088# | WA | 456ms | 24876kb | C++23 | 2.8kb | 2024-09-13 11:48:04 | 2024-09-13 11:48:04 |
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 (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() {
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9888kb
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: 456ms
memory: 24876kb
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 99966 99965 99962 99963 34 139 202 310 316 322 397 451 460 463 481 661 763 904 934 988 1219 1294 1561 1618 1684 1738 1915 2029 2290 2509 2530 2551 2695 2800 2818 2821 2914 2923 3061 3142 3154 3343 3496 3589 3784 3952 3988 4069 4504 4891 4948 5056 5197 5467 5506 5551 5752 5767 5773 5821 5905 5938...
result:
wrong answer std outputs a valid answer while participant doesn't (test case 3)