QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72899#5423. Perfect MatchingchenshiAC ✓896ms13292kbC++1.2kb2023-01-19 22:49:522023-01-19 22:50:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-19 22:50:01]
  • 评测
  • 测评结果:AC
  • 用时:896ms
  • 内存:13292kb
  • [2023-01-19 22:49:52]
  • 提交

answer

#include<cstdio>
#include<map>
using namespace std;
const int o=2e5+10;
int n,T,a[o],tot,h[o],cnt,d[o],f[o],ansx[o],ansy[o],ans,st[o],tp;bool flg;map<int,int> mp1,mp2;
struct Edge{int v,p;}e[o];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
void dfs(int nw){
	for(int i=h[nw];i;i=e[i].p) if(!d[e[i].v]) d[e[i].v]=d[nw]+1,dfs(e[i].v);
	tp=0;
	for(int i=h[nw];i;i=e[i].p)
		if(d[e[i].v]==d[nw]+1&&f[e[i].v]) ansx[++ans]=i/2,ansy[ans]=f[e[i].v];
		else if(d[e[i].v]>d[nw]) st[++tp]=i/2;
	for(int i=2;i<=tp;i+=2) ansx[++ans]=st[i-1],ansy[ans]=st[i];https://qoj.ac/contest/1093/problem/5423/statistics
	if(tp&1) f[nw]=st[tp];
}
int main(){
	for(scanf("%d",&T);T--;mp1.clear(),mp2.clear(),tot=ans=flg=0){
		scanf("%d",&n);cnt=1;
		for(int i=1,x,y;i<=n;++i){
			scanf("%d",&a[i]);
			if(mp1.find(a[i]-i)==mp1.end()) mp1[a[i]-i]=++tot;
			if(mp2.find(a[i]+i)==mp2.end()) mp2[a[i]+i]=++tot;
			ad(x=mp1[a[i]-i],y=mp2[a[i]+i]);ad(y,x);
		}
		for(int i=1;i<=tot;++i) if(!d[i]){d[i]=1;dfs(i);if(f[i]){flg=1;break;}}
		if(flg) printf("No\n");
		else{
			printf("Yes\n");
			for(int i=1;i<=n/2;++i) printf("%d %d\n",ansx[i],ansy[i]);
		}
		for(int i=1;i<=tot;++i) h[i]=d[i]=f[i]=0;
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 7180kb

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: 362ms
memory: 11700kb

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
99983 99935
99923 99812
99794 99770
99725 99722
99704 99698
99671 99638
99626 99584
99548 99494
99485 99479
99464 99413
99410 99398
99392 99383
99377 99374
99329 99266
99248 99230
99215 99125
99092 99077
99059 99041
99026 99023
98978 98966
98951 98945
98918 98894
98891 98858
98837 98807
98768 98...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 381ms
memory: 12676kb

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
274 273
272 271
270 269
268 267
266 265
264 263
262 261
260 259
258 257
256 255
254 253
252 251
250 249
248 247
246 245
244 243
242 241
240 239
238 237
236 235
234 233
232 231
230 229
228 227
226 225
224 223
222 221
220 219
218 217
216 215
214 213
212 211
210 209
208 207
206 205
204 203
202 201
...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 896ms
memory: 13292kb

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
93510 91261
76700 98712
95876 92550
89848 84747
96623 94849
94038 61276
82122 93325
28396 84243
94056 95227
39359 36251
71289 71370
85921 44268
99057 98029
74620 64062
86137 36936
86946 71229
37075 88100
71019 75550
83527 70855
91043 67727
97958 73900
58148 71786
57480 56640
88815 72958
96674 93...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 215ms
memory: 7272kb

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
988 986
982 968
962 961
958 957
951 941
935 933
912 901
898 897
896 879
875 866
862 857
856 852
843 833
823 811
810 809
808 803
799 795
785 783
777 775
774 770
769 767
761 758
755 752
747 739
737 730
727 720
718 715
706 704
703 702
701 699
694 670
663 660
659 654
653 646
638 63...

result:

ok 1000 Cases (1000 test cases)