QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#561839 | #5423. Perfect Matching | louhao088# | TL | 2ms | 12048kb | C++23 | 2.7kb | 2024-09-13 11:27:15 | 2024-09-13 11:27:17 |
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());
}
}
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;
}
int main()
{
int t = read();
while (t--) slove();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 12048kb
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
Time Limit Exceeded
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...