QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726076#5423. Perfect MatchingCode_quantumWA 320ms29420kbC++141.7kb2024-11-08 21:31:192024-11-08 21:31:19

Judging History

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

  • [2024-11-08 21:31:19]
  • 评测
  • 测评结果:WA
  • 用时:320ms
  • 内存:29420kb
  • [2024-11-08 21:31:19]
  • 提交

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)