QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726087 | #5423. Perfect Matching | Code_quantum | WA | 388ms | 32132kb | C++14 | 1.7kb | 2024-11-08 21:34:12 | 2024-11-08 21:34:13 |
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 fa){
vis[u] = true; res += d[u]; tmp[u].clear();
for(auto now: g[u]){
int v = now.px, id = now.py;
if(v == fa) continue;
if(vis[v]){
tmp[u].pb(id); continue;
}
int gt = dfs(v, u); tmp[u].pb(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){
return tmp[u].back();
}
return 0;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 16108kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 5 2 6 3 Yes 4 2 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 388ms
memory: 32132kb
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 309 308 315 314 321 320 396 395 450 449 459 458 462 461 480 479 567 566 660 659 903 902 933 932 978 977 987 986 1089 1088 1104 1103 1218 1217 1293 1292 1458 1457 1530 1529 1554 1553 1560 1559 1617 1616 1668 1667 1683 1682 1722 1721 1737 1736 2025 2024 2028 2027 2154 2153 21...
result:
wrong answer abs(99703-99653) != abs(a[99703]-a[99653]) (test case 1)