QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726120#5423. Perfect MatchingCode_quantumTL 3ms16768kbC++141.8kb2024-11-08 21:44:002024-11-08 21:44:02

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 21:44:02]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:16768kb
  • [2024-11-08 21:44:00]
  • 提交

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], dep[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] && dep[v] < dep[u]){tmp[u].pb(id); continue;}
		dep[v] = dep[u] + 1;
		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] = dep[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: 3ms
memory: 16768kb

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
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...

output:


result: