QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744698#5423. Perfect MatchingDengDuckAC ✓352ms67232kbC++141.4kb2024-11-13 22:54:192024-11-13 22:54:23

Judging History

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

  • [2024-11-13 22:54:23]
  • 评测
  • 测评结果:AC
  • 用时:352ms
  • 内存:67232kb
  • [2024-11-13 22:54:19]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
int n,A[N],Flg,D[N];
vector<int>L,R;
unordered_map<int,int>Ma[2];
struct Edge{int v,Id;};
vector<Edge>E[N],Ans;
int Dfs(int u,int f,int Lst)
{
	D[u]=D[f]+1;
	vector<int>e;
	for(Edge i:E[u])
	{
		if(i.v==f)continue;
		if(D[i.v])
		{
			if(D[i.v]<D[u])e.pb(i.Id);
		}
		else
		{
			int K=Dfs(i.v,u,i.Id);
			if(K!=-1)e.pb(K);
		}
	}
	while(e.size()>1)
	{
		int x=e.back();e.pop_back();
		int y=e.back();e.pop_back();
		Ans.pb({x,y});
	}
	if(e.size())
	{
		if(Lst==-1)Flg=0;
		Ans.pb({Lst,e.back()});
		return -1;
	}
	return Lst;
}
inline void Work()
{
	L.clear(),R.clear();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&A[i]);
		L.pb(i-A[i]),R.pb(i+A[i]);
	}
	sort(L.begin(),L.end()),sort(R.begin(),R.end());
	L.erase(unique(L.begin(),L.end()),L.end());
	R.erase(unique(R.begin(),R.end()),R.end());
	int m1=L.size(),m2=R.size();
	for(int i=0;i<m1;i++)Ma[0][L[i]]=i;
	for(int i=0;i<m2;i++)Ma[1][R[i]]=i;
	for(int i=0;i<m1+m2;i++)E[i].clear();
	for(int i=1;i<=n;i++)
	{
		int l=Ma[0][i-A[i]],r=m1+Ma[1][i+A[i]];
		E[l].pb({r,i}),E[r].pb({l,i});
	}
	Flg=1,Ans.clear();
	memset(D,0,sizeof(D));
	for(int i=0;i<m1+m2;i++)if(!D[i])Dfs(i,0,-1);
	if(!Flg)return puts("No"),void();
	puts("Yes");
	for(Edge i:Ans)printf("%d %d\n",i.v,i.Id);
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)Work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9220kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 226ms
memory: 27144kb

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

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 9524kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

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

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 352ms
memory: 27032kb

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

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 118ms
memory: 9724kb

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

result:

ok 1000 Cases (1000 test cases)