QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662744#5423. Perfect MatchingocharinAC ✓351ms24480kbC++201.6kb2024-10-21 09:47:442024-10-21 09:47:47

Judging History

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

  • [2024-10-21 09:47:47]
  • 评测
  • 测评结果:AC
  • 用时:351ms
  • 内存:24480kb
  • [2024-10-21 09:47:44]
  • 提交

answer

/*

								_/                                      _/
	   _/_/        _/_/_/      _/_/_/        _/_/_/      _/  _/_/               _/_/_/
	_/    _/    _/            _/    _/    _/    _/      _/_/          _/       _/    _/
   _/    _/    _/            _/    _/    _/    _/      _/            _/       _/    _/
	_/_/        _/_/_/      _/    _/      _/_/_/      _/            _/       _/    _/

*/
#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0;i<n;++i) cin>>a[i];
	unordered_map<int,int>mp1,mp2;
	int c1=0,c2=n;
	vector<vector<array<int,2>>>e(2*n);
	for(int i=0;i<n;++i){
		int u=i-a[i],v=i+a[i];
		if(!mp1.count(u)) mp1[u]=c1++;
		if(!mp2.count(v)) mp2[v]=c2++;
		u=mp1[u],v=mp2[v];
		e[u].push_back({v,i+1});
		e[v].push_back({u,i+1});
	}
	vector<array<int,2>>res;
	vector<int>dep(2*n),vis(2*n);
	auto dfs=[&](auto dfs,int u)->int{
		vis[u]=1;
		int cur=0;
		for(auto [v,w]:e[u]){
			if(vis[v]){
				if(dep[v]<=dep[u]) continue;
				if(!cur){
					cur=w;
				}
				else{
					res.push_back({cur,w});
					cur=0;
				}
			}
			else{
				dep[v]=dep[u]+1;
				int x=dfs(dfs,v);
				if(x){
					res.push_back({x,w});
				}
				else{
					if(cur){
						res.push_back({w,cur});
						cur=0;
					}
					else cur=w;
				}
			}
		}
		return cur;
	};
	for(int i=0;i<2*n;++i){
		if(!vis[i]) dfs(dfs,i);
	}
	if(res.size()*2==n){
		cout<<"Yes\n";
		for(auto [x,y]:res) cout<<x<<" "<<y<<"\n";
	}
	else cout<<"No\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;cin>>T;
	while(T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

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
3 1
4 2
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 237ms
memory: 21408kb

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
139 79
244 202
310 289
322 316
382 337
451 397
463 460
517 481
526 520
568 556
661 619
763 736
853 790
934 904
988 979
1105 1090
1219 1162
1285 1273
1405 1294
1456 1411
1531 1459
1561 1555
1615 1588
1630 1618
1669 1651
1723 1684
1915 1738
2026 1972
2092 2029
2197 2155
2305 2290
2353 2350
2431 24...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3904kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 215ms
memory: 24480kb

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 351ms
memory: 24324kb

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
89504 28
26518 8564
63463 1121
36817 129
95315 8931
96991 61541
1725 1600
81303 70110
16772 13611
34736 778
74032 11544
88310 80993
80608 33052
37233 9560
78597 37367
84943 65442
50244 20961
91157 52881
10333 6609
19162 3408
87006 59542
97729 416
79681 23980
66364 27149
67617 10211
44140 17075
5...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 176ms
memory: 3796kb

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
4 1
9 6
17 16
21 18
25 22
31 27
33 32
42 35
51 47
64 62
79 72
86 82
96 90
103 101
109 107
121 111
145 127
155 147
159 157
166 164
174 169
179 176
192 191
201 195
210 204
229 223
237 230
246 244
260 252
269 262
282 276
293 292
295 294
297 296
303 301
306 304
318 309
329 325
338 ...

result:

ok 1000 Cases (1000 test cases)