QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726115#5423. Perfect MatchingCode_quantumWA 377ms31040kbC++141.7kb2024-11-08 21:42:272024-11-08 21:42:28

Judging History

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

  • [2024-11-08 21:42:28]
  • 评测
  • 测评结果:WA
  • 用时:377ms
  • 内存:31040kb
  • [2024-11-08 21:42: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 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]){tmp[u].pb(id); continue;}
		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] = 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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 15956kb

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
Wrong Answer
time: 377ms
memory: 31040kb

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
244 242
289 287
309 308
315 314
321 320
337 335
382 380
396 395
450 449
459 458
462 461
480 479
517 515
520 518
526 524
556 554
567 566
619 617
660 659
736 734
763 761
790 788
853 851
903 902
933 932
978 977
987 986
1089 1088
1104 1103
1162 1160
1218 1217
1273 1271
1285 128...

result:

wrong answer 99870 appears more than once (test case 1)