QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706259#5423. Perfect MatchingCSQAC ✓2271ms26436kbC++172.2kb2024-11-03 09:50:282024-11-03 09:50:29

Judging History

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

  • [2024-11-03 09:50:29]
  • 评测
  • 测评结果:AC
  • 用时:2271ms
  • 内存:26436kb
  • [2024-11-03 09:50:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i < b;i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x.size())
typedef long long int ll;
typedef pair<ll,ll> pii;
typedef vector<int> vi;
#define fi first
#define se second
const int MAXN = 2e5+5;
map<int,vector<int>>adj[2];
map<int,int>deg[2],vis[2];
int rg[MAXN],tree[MAXN];
vector<int>comp;
void dfs(int c,int v,int p){
	if(!c)comp.push_back(v);
	vis[c][v] = 1;
	for(int x:adj[c][v]){
		if(x==p)continue;
		if(!vis[c^1][x]){
			int i = (v-x)/2;
			i = abs(i);
			tree[i] = 1;
			dfs(c^1,x,v);
		}
	}
}
void dfs2(int c,int v,int p){
	for(int x:adj[c][v]){
		if(x==p)continue;
		int i = (v-x)/2;
		i = abs(i);
		if(!tree[i])continue;
		dfs2(c^1,x,v);
		if(deg[c^1][x]){
			rg[i] = 1;
			deg[c][v] ^= 1;
		}
	}
	
	
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		bool ok = 1;
		vector<int>a(n);
		for(int i=0;i<n;i++)cin>>a[i];
		for(int i=0;i<2;i++){
			adj[i].clear();
			vis[i].clear();
			deg[i].clear();
		}
		for(int i=0;i<n;i++)rg[i] = tree[i] = 0;
		
		for(int i=0;i<n;i++){
			adj[0][a[i]-i].push_back(a[i]+i);
			adj[1][a[i]+i].push_back(a[i]-i);
		}
		for(auto x:adj[0])deg[0][x.fi] = sz(x.se)%2;
		for(int i=0;i<n;i++){
			if(vis[0][a[i]-i])continue;
			comp.clear();
			dfs(0,a[i]-i,-2e9);
			int sum = 0;
			for(int v:comp){
				sum += deg[0][v];
				for(int x:adj[0][v]){
					int j = (v-x)/2;
					j = abs(j);
					if(!tree[j]){
						rg[j] = 1;
						deg[0][v] ^= 1;
						deg[1][x] ^= 1;
					}
				}
			}
			dfs2(0,comp[0],-2e9);
			if(sum&1){
				ok = 0;
				break;
			}
		}
		if(!ok){
			cout<<"No"<<'\n';
			continue;
		}
		map<int,vector<int>>l,r;
		for(int i=0;i<n;i++){
			//cout<<a[i]-i<<" "<<a[i]+i<<" "<<rg[i]<<'\n';
			if(rg[i])r[a[i]+i].push_back(i);
			else l[a[i]-i].push_back(i);
		}
		cout<<"Yes"<<'\n';
		for(auto x:l){
			vector<int>v = x.se;
			for(int i=0;i<sz(v);i+=2){
				cout<<v[i]+1<<" "<<v[i+1]+1<<'\n';
			}
		}
		for(auto x:r){
			vector<int>v = x.se;
			for(int i=0;i<sz(v);i+=2){
				cout<<v[i]+1<<" "<<v[i+1]+1<<'\n';
			}
		}
	}
		
	
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 773ms
memory: 20940kb

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
140 142
34 79
139 202
310 316
322 397
451 460
463 481
568 661
904 934
979 988
1090 1105
1219 1294
1459 1531
1555 1561
1618 1669
1684 1723
1738 2026
2029 2155
2197 2290
2419 2485
2509 2530
2551 2602
2692 2695
2800 2818
2821 2890
2914 2923
3061 3142
3154 3343
3496 3589
3784 3916
3952 3988
4060 406...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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
35 36
37 38
1 2
3 4
5 6
7 8
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
69 70
71 72
73 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 835ms
memory: 26436kb

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
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 71778
71779 71780
71781 71782
71783 71784
71785 71786
71787 71788
71789 71790
71791 71792
71793 71794
71795 71796
71797 71798
71799 71800
71801 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 2271ms
memory: 25184kb

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
99327 99702
97303 99263
95828 96046
95341 97927
93823 98919
97616 97711
93730 94937
95342 98589
93180 97318
92136 96630
93829 95270
94735 96521
91620 94320
92059 92301
91889 93560
93095 95731
91882 96890
90459 91338
97295 98433
90174 92734
96660 99305
98913 99486
93567 98857
89088 98883
92401 98...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 424ms
memory: 3892kb

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
2 8
10 19
44 52
60 63
80 84
95 97
100 115
117 140
168 189
196 197
206 209
216 217
218 234
238 239
247 248
253 258
264 265
281 290
305 322
327 353
360 362
369 379
380 408
420 430
441 448
457 475
479 481
488 493
495 496
498 526
531 532
534 541
556 562
567 569
571 582
595 621
622 ...

result:

ok 1000 Cases (1000 test cases)