QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732536#5423. Perfect MatchingPorNPtreeAC ✓481ms25140kbC++231.6kb2024-11-10 15:03:442024-11-10 15:03:48

Judging History

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

  • [2024-11-10 15:03:48]
  • 评测
  • 测评结果:AC
  • 用时:481ms
  • 内存:25140kb
  • [2024-11-10 15:03:44]
  • 提交

answer

#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+5;
int T,n,m,m0,m1,a[N],b[N],c[N],sz[N],fa[N];
vector<P>g[N],ans;bool v[N],ban[N];
inline int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
inline void hb(int x,int y)
{
	x=getf(x),y=getf(y);sz[x]++;
	if(x^y) fa[y]=x,sz[x]+=sz[y];
}
inline void add(int u,int v,int w)
{
	hb(u,v);//cout<<u<<" "<<v<<" "<<w<<"\n";
	g[u].push_back({v,w}),g[v].push_back({u,w});
}
inline bool chk()
{
	for(int i=1;i<=m;i++) if(sz[getf(i)]&1) return 0;
	return 1;
}
void dfs(int x,int las)
{
	v[x]=1;
	for(auto [y,w]:g[x]) if(!v[y]) dfs(y,w);
	vector<int>nw;
	for(auto [y,w]:g[x]) if(!ban[w]&&w!=las) nw.push_back(w);
	if(nw.size()&1) nw.push_back(las);
	for(int i:nw) ban[i]=1;
	for(int i=0;i<nw.size()/2;i++) ans.push_back({nw[i<<1],nw[i<<1|1]});
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
	while(T--)
	{
		cin>>n;m0=m1=0;ans.clear();
		for(int i=1;i<=n;i++) cin>>a[i],b[++m0]=i-a[i],c[++m1]=i+a[i],ban[i]=0;
		sort(b+1,b+1+m0);m0=unique(b+1,b+1+m0)-b-1;
		sort(c+1,c+1+m1);m1=unique(c+1,c+1+m1)-c-1;
		m=m0+m1;
		for(int i=1;i<=m;i++) fa[i]=i,sz[i]=0,g[i].clear(),v[i]=0;
		#define ls1(x) lower_bound(b+1,b+1+m0,x)-b
		#define ls2(x) lower_bound(c+1,c+1+m1,x)-c
		for(int i=1;i<=n;i++) add(ls1(i-a[i]),m0+ls2(i+a[i]),i);
		if(!chk()){cout<<"No\n";continue;}
		for(int i=1;i<=m;i++) if(!v[i]) dfs(i,0);
		cout<<"Yes\n";
		for(auto [u,v]:ans) cout<<u<<" "<<v<<"\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7864kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 246ms
memory: 17924kb

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
21 22
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
12...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 193ms
memory: 25140kb

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
49559 49560
29353 29354
29355 29356
29357 29358
29359 29360
29361 29362
29363 29364
29365 29366
29367 29368
29369 29370
29371 29372
29373 29374
29375 29376
29377 29378
29379 29380
29381 29382
29383 29384
29385 29386
29387 29388
29389 29390
29391 29392
29393 29394
29395 29396
29397 29398
33954 33...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 481ms
memory: 18740kb

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
36811 36817
8931 95315
96991 61541
70110 81303
13611 16772
34736 778
88310 80993
821 11544
74032 940
33052 80608
9050 10585
78597 37367
41232 65442
84943 50244
91157 52881
5417 10333
18933 19162
3408 59542
87006 97729
79681 23980
27149 66364
67617 10211
17075 44140...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 142ms
memory: 7812kb

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
14 15
57 59
66 67
77 78
98 99
129 130
142 144
161 162
165 167
183 185
184 186
198 199
200 202
205 207
214 215
232 233
243 245
270 271
279 280
284 286
307 308
312 314
315 316
320 321
328 330
332 333
370 372
384 385
387 388
412 413
421 422
424 426
427 428
432 433
435 436
440 442
...

result:

ok 1000 Cases (1000 test cases)