QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99961#5423. Perfect Matching1kriAC ✓1617ms46600kbC++141.4kb2023-04-24 08:54:382023-04-24 08:54:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-24 08:54:40]
  • 评测
  • 测评结果:AC
  • 用时:1617ms
  • 内存:46600kb
  • [2023-04-24 08:54:38]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
int t,n,a[200005];
int tot1,tot2;
map<int,int> id1,id2;
vector<int> e[400005],e_id[400005];
int depth[400005];
int ans[200005][2],tot;
void add(int x,int y){
	++tot;
	ans[tot][0]=x,ans[tot][1]=y;
	return;
}
int dfs(int now,int fa,int d){
	depth[now]=d;
	int qwq=-1;
	for (int i=0;i<(int)e[now].size();i++){
		int v=e[now][i],w=e_id[now][i];
		if (v==fa)continue;
		if (depth[v]==0){
			int t=dfs(v,now,d+1);
			if (t!=-1)add(t,w);
			else if (qwq!=-1)add(qwq,w),qwq=-1;
			else qwq=w;
		}
		else if (depth[v]<depth[now]){
			if (qwq!=-1)add(qwq,w),qwq=-1;
			else qwq=w;
		}
	}
	return qwq;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		tot1=tot2=0;
		id1.clear(),id2.clear();
		for (int i=1;i<=2*n;i++){
			e[i].clear();
			e_id[i].clear();
			depth[i]=0;
		}
		for (int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if (id1[a[i]-i]==0)id1[a[i]-i]=++tot1;
			if (id2[a[i]+i]==0)id2[a[i]+i]=++tot2;
			int x=id1[a[i]-i],y=id2[a[i]+i]+n;
			e[x].push_back(y);
			e_id[x].push_back(i);
			e[y].push_back(x);
			e_id[y].push_back(i);
		}
		tot=0;
		for (int i=1;i<=2*n;i++)
			if (depth[i]==0)dfs(i,0,1);
		if (tot==n/2){
			printf("Yes\n");
			for (int i=1;i<=tot;i++)printf("%d %d\n",ans[i][0],ans[i][1]);
		}
		else printf("No\n");
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 22556kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 597ms
memory: 33308kb

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
3 79
137 138
200 201
139 202
242 244
287 289
308 309
314 315
310 316
320 321
335 337
380 382
395 396
322 397
449 450
458 459
451 460
461 462
479 480
463 481
515 517
518 520
524 526
554 556
566 567
617 619
659 660
568 661
734 736
761 763
788 790
851 853
902 903
932 933
904 934
977 978...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 2ms
memory: 22364kb

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
1 2
3 4
5 6
7 8
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
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
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: 666ms
memory: 46600kb

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
1 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 ...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 1617ms
memory: 36820kb

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
13 14
89504 28
49 54
57 58
8564 26518
63463 1121
153 222
36811 36817
84 129
8931 95315
506 7625
536 1600
96991 61541
47 48
99 152
70110 81303
13611 16772
126 132
34736 778
62 7528
859 1003
92 127
513 768
66 118
288 2392
317 332
3113 3777
203 204
888 3225
56 59
427 479
188 559
88 100
5757 5965
82...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 227ms
memory: 22512kb

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
1 4
6 9
16 17
18 21
23 22
25 27
31 32
34 33
35 42
48 47
51 62
73 72
64 79
82 86
90 96
101 103
108 107
109 111
128 127
121 145
148 147
156 155
157 159
164 166
169 174
180 179
176 191
193 192
195 201
211 210
204 223
229 230
237 244
246 252
261 260
263 262
269 276
282 292
293 294
...

result:

ok 1000 Cases (1000 test cases)