QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726126#5423. Perfect MatchingCode_quantumAC ✓785ms40888kbC++141.8kb2024-11-08 21:45:572024-11-08 21:45:57

Judging History

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

  • [2024-11-08 21:45:57]
  • 评测
  • 测评结果:AC
  • 用时:785ms
  • 内存:40888kb
  • [2024-11-08 21:45:57]
  • 提交

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;}
		else if(vis[v]) 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: 5ms
memory: 15488kb

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: 0
Accepted
time: 403ms
memory: 31508kb

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:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 16812kb

input:

10
100
28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...

output:

Yes
58 57
56 55
54 53
52 51
50 49
48 47
46 45
44 43
42 41
39 40
34 33
32 31
30 29
100 99
98 97
96 95
94 93
92 91
90 89
88 87
86 85
84 83
82 81
80 79
78 77
76 75
28 27
26 25
24 23
22 21
20 19
18 17
16 15
14 13
12 11
10 9
68 67
66 65
64 63
62 61
60 59
38 37
35 36
8 7
6 5
4 3
1 2
74 73
72 71
70 69
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 377ms
memory: 40888kb

input:

10
100000
-40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...

output:

Yes
29352 29351
29350 29349
29348 29347
29346 29345
29344 29343
29342 29341
29340 29339
29338 29337
29336 29335
29334 29333
29332 29331
29330 29329
72010 72009
72008 72007
72006 72005
72004 72003
72002 72001
72000 71999
71998 71997
71996 71995
71994 71993
71992 71991
71990 71989
71988 71987
71986 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 785ms
memory: 31048kb

input:

10
100000
0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...

output:

Yes
28 89504
63463 26518
1121 8564
36817 36811
95315 8931
61541 96991
92548 81132
83637 41302
778 34736
4360 12537
2005 99552
92893 97953
30631 58176
19622 70597
26691 37677
67617 66364
10211 27149
57643 44140
11472 17075
95323 35741
12598 23176
10585 9050
28519 68565
10746 21782
63141 47710
5564 17...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 191ms
memory: 16108kb

input:

1000
1000
-2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...

output:

No
No
No
No
No
No
Yes
22 23
33 34
47 48
72 73
107 108
127 128
147 148
155 156
179 180
192 193
210 211
260 261
262 263
309 310
318 319
342 343
404 405
406 407
417 418
443 444
455 456
502 503
583 584
599 600
663 664
699 700
704 705
718 719
720 721
727 728
739 740
770 771
857 858
912 913
951 952
962 96...

result:

ok 1000 Cases (1000 test cases)