QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#272350#5423. Perfect Matchingushg8877AC ✓777ms104748kbC++141.5kb2023-12-02 16:58:582023-12-02 16:58:59

Judging History

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

  • [2023-12-02 16:58:59]
  • 评测
  • 测评结果:AC
  • 用时:777ms
  • 内存:104748kb
  • [2023-12-02 16:58:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=1e6+5;
map<ll,int> M;int tot=0;
int ls[MAXN],rs[MAXN];
vector<pair<int,int> > ve[2*MAXN];// 到达节点,边编号 
vector<int> ans[MAXN];
int n;int a[MAXN];bool vis[MAXN];
bool dfs(int u,int fa){// 是否用完 
	vis[u]=1;
	for(auto i:ve[u]){
		if(i.first==fa) continue;
		if(vis[i.first]) ans[u].push_back(i.second);
	}
	for(auto i:ve[u]){
		if(vis[i.first]) continue;
		if(dfs(i.first,u)) ans[i.first].push_back(i.second);
		else ans[u].push_back(i.second);
	}
	return ans[u].size()&1; 
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	M.clear();tot=0;
	for(int i=1;i<=n;i++){
		if(!M[a[i]+i])
			M[a[i]+i]=++tot;
		ls[i]=M[a[i]+i];
	}
	M.clear();
	for(int i=1;i<=n;i++){
		if(!M[a[i]-i])
			M[a[i]-i]=++tot;
		rs[i]=M[a[i]-i];
	}
	for(int i=1;i<=tot;i++) ve[i].clear();
	for(int i=1;i<=n;i++){
		ve[ls[i]].push_back(MP(rs[i],i));
		ve[rs[i]].push_back(MP(ls[i],i));
	}
	for(int i=1;i<=tot;i++) ans[i].clear(),vis[i]=0;
	for(int i=1;i<=tot;i++)
		if(!vis[i]) dfs(i,0);
	for(int i=1;i<=tot;i++)
		if(ans[i].size()&1){
			cout<<"No"<<endl;
			return;
		}
	cout<<"Yes"<<endl;
	for(int i=1;i<=tot;i++)
		for(int j=0;j<ans[i].size();j+=2)
			cout<<ans[i][j]<<" "<<ans[i][j+1]<<endl;
	return; 
}
int main(){
//	freopen("input.in","r",stdin);
//	freopen("answer.out","w",stdout);
	ios::sync_with_stdio(false);
	int _;cin>>_;
	while(_--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 77144kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 379ms
memory: 93084kb

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
1 4
6 8
9 10
13 17
18 19
26 27
28 35
59 60
61 85
89 92
108 110
111 112
113 114
115 119
125 131
132 133
134 135
136 143
144 145
153 161
181 186
194 199
204 212
217 218
219 220
221 222
223 230
231 232
234 271
296 297
298 305
306 307
326 329
334 338
341 342
343 347
350 359
360 361
363 390
411 415
4...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 4ms
memory: 79360kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 387ms
memory: 104748kb

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
491 492
493 494
495 496
497 498
499 500
501 502
503 504
505 506
507 508
509 510
511 512
513 514
515 516
517 518
519 520
521 522
523 524
525 526
527 528
529 530
531 532
533 534
535 536
537 538
539 540
541 542
543 544
545 546
547 548
549 550
551 552
553 554
555 556
557 558
559 560
561 562
563 564
...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 777ms
memory: 94036kb

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
1 1932
1986 3820
8799 9282
9393 9892
13027 13900
17031 20491
20817 22113
31175 32797
34960 39303
45082 59024
61232 71444
76524 76759
78974 79799
80672 84250
93166 98041
99492 99604
547 737
1906 1981
4601 5174
8124 12688
15695 17854
18985 19323
19798 23994
24756 26145
26228 26307
26872 27305
3142...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 203ms
memory: 77440kb

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
15 14
23 22
34 33
36 37
48 47
59 57
67 66
73 72
75 74
78 77
99 98
108 107
113 112
128 127
130 131
144 142
148 147
152 151
156 155
162 161
167 165
171 170
180 179
185 183
186 184
193 192
199 198
202 200
207 205
211 210
213 212
215 214
221 220
233 232
245 243
261 260
263 262
267 ...

result:

ok 1000 Cases (1000 test cases)