QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726107 | #5423. Perfect Matching | Code_quantum | RE | 0ms | 0kb | C++14 | 1.8kb | 2024-11-08 21:39:27 | 2024-11-08 21:39:27 |
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();
int inid = 0;
for(auto now: g[u]){
int v = now.px, id = now.py;
if(v == fa){
inid = id; 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){
ans.pb({inid, tmp[u].back()});
return 0;
}
return tmp[u].back();
}
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: 0
Runtime Error
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7