QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726115 | #5423. Perfect Matching | Code_quantum | WA | 377ms | 31040kb | C++14 | 1.7kb | 2024-11-08 21:42:27 | 2024-11-08 21:42:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define px first
#define py second
#define pb push_back
const int N = 200005;
int n, res, a[N], d[N], barl[N], barr[N];
map<int, int> mpl, mpr;
vector<pii> g[N], ans; vector<int> tmp[N]; bool vis[N];
int dfs(int u, int in){
vis[u] = true; res += d[u]; tmp[u].clear();
for(auto now: g[u]){
int v = now.px, id = now.py;
if(id == in) continue;
if(vis[v]){tmp[u].pb(id); continue;}
int gt = dfs(v, id);
if(gt) tmp[u].pb(gt);
}
while((int)tmp[u].size() > 1){
int x = tmp[u].back(); tmp[u].pop_back();
int y = tmp[u].back(); tmp[u].pop_back();
ans.pb({x, y});
}
if((int)tmp[u].size() & 1){
ans.pb({in, tmp[u].back()});
return 0;
}
return in;
}
void work(){
scanf("%d", &n); int cntl = 0, cntr = 0;
mpl.clear(); mpr.clear(); ans.clear();
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
barl[++ cntl] = a[i] + i;
barr[++ cntr] = a[i] - i;
}
sort(barl + 1, barl + cntl + 1);
cntl = unique(barl + 1, barl + cntl + 1) - barl - 1;
sort(barr + 1, barr + cntr + 1);
cntr = unique(barr + 1, barr + cntr + 1) - barr - 1;
for(int i = 1; i <= cntl; i ++) mpl[barl[i]] = i;
for(int i = 1; i <= cntr; i ++) mpr[barr[i]] = i;
for(int i = 1; i <= cntl + cntr; i ++){
g[i].clear(); d[i] = 0; vis[i] = false;
}
for(int i = 1; i <= n; i ++){
int x = mpl[a[i] + i], y = mpr[a[i] - i] + cntl;
g[x].pb({y, i}); g[y].pb({x, i}); d[x] ++; d[y] ++;
}
for(int i = 1; i <= cntl + cntr; i ++) if(! vis[i]){
res = 0; dfs(i, 0); if((res / 2) & 1){puts("No"); return;}
}
puts("Yes");
for(auto now: ans) printf("%d %d\n", now.px, now.py);
}
int main(){
int t; scanf("%d", &t);
while(t --) work(); return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 15956kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 2 5 3 6 Yes 2 4 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 377ms
memory: 31040kb
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 78 77 138 137 201 200 244 242 289 287 309 308 315 314 321 320 337 335 382 380 396 395 450 449 459 458 462 461 480 479 517 515 520 518 526 524 556 554 567 566 619 617 660 659 736 734 763 761 790 788 853 851 903 902 933 932 978 977 987 986 1089 1088 1104 1103 1162 1160 1218 1217 1273 1271 1285 128...
result:
wrong answer 99870 appears more than once (test case 1)