QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726076 | #5423. Perfect Matching | Code_quantum | WA | 320ms | 29420kb | C++14 | 1.7kb | 2024-11-08 21:31:19 | 2024-11-08 21:31:19 |
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){
vis[u] = true; res += d[u]; tmp[u].clear();
for(auto now: g[u]){
int v = now.px, id = now.py;
if(vis[v]) continue;
int gt = dfs(v); 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); if((res / 2) & 1){puts("No"); return;}
}
puts("Yes");
assert(ans.size() <= n / 2);
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: 0ms
memory: 14384kb
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: 320ms
memory: 29420kb
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 99997 99979 99823 99808 99730 99703 99655 99649 99583 99571 99547 99541 99514 99508 99490 99454 99322 99277 99256 99220 99190 99187 99163 99148 99145 99115 99085 99070 99031 98992 98941 98938 98935 98890 98785 98758 98719 98680 98509 98467 98419 98377 98362 98329 98257 98218 98176 98146 98134 98...
result:
wrong output format Expected integer, but "Yes" found (test case 1)