QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724873#5423. Perfect MatchingErinyesWA 956ms30036kbC++141.2kb2024-11-08 15:25:032024-11-08 15:25:03

Judging History

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

  • [2024-11-08 15:25:03]
  • 评测
  • 测评结果:WA
  • 用时:956ms
  • 内存:30036kb
  • [2024-11-08 15:25:03]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=3e5+5;
int n,tot,cnt;
int a[N],vst[N],del[N];
map<int,int>A,B;
vector<int>son[N];
vector<pair<int,int>>ans;
void dfs(int x,int fa){
	vst[x]=1,cnt+=x<=n;
	vector<int> d;
	for(int y:son[x]){
		if(!vst[y]){
			dfs(y,x);
			if(x>n&&!del[y])d.push_back(y);
		}
	}
	if(x>n){
		for(int i=0;i+1<d.size();i+=2)ans.push_back({d[i],d[i+1]});
		if(d.size()&1){
			if(fa&&!del[fa])ans.push_back({d.back(),fa}),del[fa]=1;
		}
	}
}
inline void solve(){
	cin>>n,tot=n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(A.find(a[i]+i)==A.end())A[a[i]+i]=++tot;
		if(B.find(a[i]-i)==B.end())B[a[i]-i]=++tot;
		son[i].push_back({A[a[i]+i]}),son[A[a[i]+i]].push_back(i);
		son[i].push_back({B[a[i]-i]}),son[B[a[i]-i]].push_back(i);
	}
	for(int i=1;i<=tot;i++){
		if(vst[i])continue;
		cnt=0,dfs(i,0);
		if(cnt&1)return cout<<"No\n",void();
	}
	cout<<"Yes\n";
	for(auto t:ans)cout<<t.first<<' '<<t.second<<endl;
	for(int i=1;i<=tot;i++)son[i].clear(),vst[i]=del[i]=0;
	ans.clear(),A.clear(),B.clear();
}
signed main(){
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	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: 3ms
memory: 12676kb

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: 377ms
memory: 23452kb

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

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 12624kb

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 3
4 5
6 7
8 1
10 11
12 13
14 15
16 17
18 19
20 21
22 23
24 25
26 27
28 9
30 31
32 33
34 29
36 37
38 35
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
58 39
60 61
62 63
64 65
66 67
68 59
70 71
72 73
74 69
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 75
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 411ms
memory: 30036kb

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 3
4 5
6 7
8 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 35
36 37
38 39
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
58 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 101
10...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 956ms
memory: 27248kb

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

result:

ok 10 Cases (10 test cases)

Test #6:

score: -100
Wrong Answer
time: 225ms
memory: 13036kb

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
Yes
29 27
37 35
55 53
9 8
48 47
57 56
59 58
64 65
89 90
92 93
115 116
119 120
122 121
129 130
134 136
140 141
151 150
162 163
168 169
185 184
187 186
190 189
191 192
216 218
219 220
221 222
229 230
237 236
244 245
249 250
269 268
274 273
284 285
316 317
320 322
361 360
365 364
379 378
418 419
...

result:

wrong answer abs(37-35) != abs(a[37]-a[35]) (test case 3)