QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733639#5423. Perfect MatchingEason2009AC ✓884ms29808kbC++141.4kb2024-11-10 20:16:572024-11-10 20:16:58

Judging History

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

  • [2024-11-10 20:16:58]
  • 评测
  • 测评结果:AC
  • 用时:884ms
  • 内存:29808kb
  • [2024-11-10 20:16:57]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=200005;
int _,n,m,a[N],dep[N],cnt;
vector<pii>e[N];
map<int,int>mp1,mp2;
pii ans[N];
int dfs(int u,int fa)
{
	vector<int>nw;
	dep[u]=dep[fa]+1;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i].fi,id=e[u][i].se;
		if(v==fa) continue;
		if(dep[v])
		{
			if(dep[v]>dep[u]) nw.pb(id);
			continue;
		}
		int p=dfs(v,u);
		if(p) ans[++m]={p,id};
		else nw.pb(id);
	}
	int res=0;
	if(nw.size()%2==1) res=nw.back(),nw.pop_back();
	for(int i=0;i<nw.size();i+=2) ans[++m]={nw[i],nw[i+1]};
	return res;
}
void solve()
{
	m=0;
	mp1.clear();
	mp2.clear();
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],mp1[a[i]-i]=1,mp2[a[i]+i]=1;
	cnt=0;
	for(auto u:mp1) mp1[u.fi]=++cnt;
	for(auto u:mp2) mp2[u.fi]=++cnt;
	for(int i=1;i<=cnt;i++) e[i].clear(),dep[i]=0;
	for(int i=1;i<=n;i++)
	{
		int x=mp1[a[i]-i],y=mp2[a[i]+i];
		e[x].pb({y,i});
		e[y].pb({x,i});
	}
	for(int i=1;i<=cnt;i++)
	{
		if(dep[i]) continue;
		if(dfs(i,0))
		{
			cout<<"No"<<'\n';
			return;
		}
	}
	cout<<"Yes"<<'\n';
	for(int i=1;i<=m;i++) cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
	return;
}
int main()
{
	//freopen("matching.in","r",stdin);
	//freopen("matching.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>_;
	while(_--) solve();
	return 0;
}

详细

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 344ms
memory: 24684kb

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
79 139
202 244
289 310
316 322
337 382
397 451
460 463
481 517
520 526
556 568
619 661
736 763
790 853
904 934
979 988
1090 1105
1162 1219
1273 1285
1294 1405
1411 1456
1459 1531
1555 1561
1588 1615
1618 1630
1651 1669
1684 1723
1738 1915
1972 2026
2029 2092
2155 2197
2290 2305
2350 2353
2419 24...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 360ms
memory: 29808kb

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
29329 29330
29331 29332
29333 29334
29335 29336
29337 29338
29339 29340
29341 29342
29343 29344
29345 29346
29347 29348
29349 29350
29351 29352
71753 71754
71755 71756
71757 71758
71759 71760
71761 71762
71763 71764
71765 71766
71767 71768
71769 71770
71771 71772
71773 71774
71775 71776
71777 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 884ms
memory: 22484kb

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
8564 26518
63463 1121
36817 129
8931 95315
89504 28
70110 81303
13611 16772
34736 778
88310 80993
11544 74032
33052 80608
3199 1661
47380 3633
3408 19162
59542 87006
97729 416
62860 73052
35450 56229
55641 9450
99552 2005
84101 4926
81132 92548
41302 83637
92168 28333
71221 3610
78597 37367
6544...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 225ms
memory: 10108kb

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
3 5
26 28
29 38
41 43
45 49
57 68
70 71
74 83
87 112
118 119
122 124
126 129
134 139
141 142
143 146
151 165
170 175
177 178
183 184
200 203
205 208
212 219
220 226
243 257
266 268
270 273
274 277
284 285
298 300
312 313
323 324
326 328
332 335
339 345
354 359
361 365
366 370
3...

result:

ok 1000 Cases (1000 test cases)