QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733518#5423. Perfect MatchingoxcoxsgaAC ✓447ms42352kbC++142.0kb2024-11-10 19:35:552024-11-10 19:35:56

Judging History

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

  • [2024-11-10 19:35:56]
  • 评测
  • 测评结果:AC
  • 用时:447ms
  • 内存:42352kb
  • [2024-11-10 19:35:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MaxN=1000000;
int n,a[MaxN+1],btr=0;
vector<int>g[MaxN+1];
bool vst[MaxN+1];
vector<pair<int,int>>ans;
pair<vector<int>,bool>DFS(int u,int prt){
	vst[u]=true;
	vector<int>clt;
	for(int v:g[u]){
		if(v==prt||vst[v])continue;
		auto ret=DFS(v,u);
		auto&vec=ret.first;
		if(!ret.second)return make_pair(vector<int>(),false);
		clt.insert(clt.end(),vec.begin(),vec.end());
	}
	if(u>n){
		while(clt.size()>=2){
			ans.emplace_back(clt[clt.size()-1],clt[clt.size()-2]);
			clt.pop_back(),clt.pop_back();
		}
		return make_pair(clt,true);
	}else{
		if(clt.size()==0){
			return make_pair(vector<int>{u},true);
		}else if(clt.size()==1){
			ans.emplace_back(u,clt.back());
			return make_pair(vector<int>(),true);
		}else return make_pair(vector<int>(),false);
	}
}
void Solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	unordered_map<int,vector<int> >umap;
	for(int i=1;i<=n*3;i++)g[i].clear(),vst[i]=false;
	ans.clear();
	btr=0;
	for(int i=1;i<=n;i++)umap[a[i]+i].push_back(i);
	for(auto&pi:umap){
		if(pi.second.size()<2)continue;
		btr++;
//cout<<pi.first<<"(p):";
		for(int v:pi.second){
//			cout<<v<<' ';
			g[btr+n].push_back(v);
			g[v].push_back(btr+n);
		}
//cout<<'\n';
	}
	umap.clear();
	for(int i=1;i<=n;i++)umap[a[i]-i].push_back(i);
	for(auto&pi:umap){
		if(pi.second.size()<2)continue;
		btr++;
//cout<<pi.first<<"(n):";
		for(int v:pi.second){
//			cout<<v<<' ';
			g[btr+n].push_back(v);
			g[v].push_back(btr+n);
		}
//cout<<'\n';
	}
//	cout<<btr<<'\n';
	for(int i=1;i<=n;i++){
		if(vst[i])continue;
		auto ret=DFS(i,0);
		if(!ret.second||ret.first.size()){
			cout<<"No\n";
			return;
		}
	}
	cout<<"Yes\n";
	for(auto&pi:ans)cout<<pi.first<<' '<<pi.second<<'\n';
}
/*
1
7
1 4 1 10 1 1 7
*/
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin.tie(0)->sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
		Solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 28236kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
1 4
2 5
3 6
Yes
1 3
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 265ms
memory: 40664kb

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: 4ms
memory: 28408kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 212ms
memory: 38748kb

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
274 273
272 271
270 269
268 267
266 265
264 263
262 261
260 259
258 257
256 255
254 253
252 251
250 249
248 247
246 245
244 243
242 241
240 239
238 237
236 235
234 233
232 231
230 229
228 227
226 225
224 223
222 221
220 219
218 217
216 215
214 213
212 211
210 209
208 207
206 205
204 203
202 201
...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 447ms
memory: 42352kb

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
81303 70110
16772 13611
778 34736
73052 62860
56229 35450
80993 88310
74032 11544
940 821
80608 33052
80963 80784
50011 57649
67617 66364
10211 27149
57643 44140
11472 17075
95323 35741
12598 23176
24308 921
92548 81132
83637 41302
28333 92168
3610 71221
37367 7859...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 174ms
memory: 28448kb

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)