QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726087#5423. Perfect MatchingCode_quantumWA 388ms32132kbC++141.7kb2024-11-08 21:34:122024-11-08 21:34:13

Judging History

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

  • [2024-11-08 21:34:13]
  • 评测
  • 测评结果:WA
  • 用时:388ms
  • 内存:32132kb
  • [2024-11-08 21:34:12]
  • 提交

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)