QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128998#5423. Perfect MatchingPetroTarnavskyi#AC ✓837ms38192kbC++172.1kb2023-07-21 18:45:402023-07-21 18:45:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-21 18:45:43]
  • 评测
  • 测评结果:AC
  • 用时:837ms
  • 内存:38192kb
  • [2023-07-21 18:45:40]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 1 << 17;

set<int> nused[N][2];
int used[N];
int x[N], y[N];

vector<PII> ans;

int dfs(int v, int par){
	auto& L = nused[x[v]][0];
	auto& R = nused[y[v]][1];
	
	used[v] = 1;
	L.erase(v);
	R.erase(v);
	
	int l = -1;
	if(SZ(L) != 0){
		int to = *L.begin();
		l = dfs(to, v);
	}
	
	int r = -1;
	if(SZ(R) != 0){
		int to = *R.begin();
		r = dfs(to, v);
	}
	if(l == -1 && r == -1)
		return v;

	if(l == -1){
		ans.PB({v, r});
		return -1;
	}
	if(r == -1){
		ans.PB({v, l});
		return -1;
	}
	
	if(par == -1)
		return -1;
	
	if(x[v] == x[par]){
		ans.PB({v, r});		
		return l;
	}
	if(y[v] == y[par]){
		ans.PB({v, l});		
		return r;
	}
		
	
	assert(0);
	return -1;
}

void solve(){
	int n;
	cin >> n;
	
	VI a(n);
	FOR(i, 0, n)
	{
		cin >> a[i];
		x[i] = a[i] - i;
		y[i] = a[i] + i;
	}
	VI v(x, x + n);
	sort(ALL(v));
	FOR (i, 0, n) x[i] = lower_bound(ALL(v), x[i]) - v.begin();
	v = VI(y, y + n);
	sort(ALL(v));
	FOR (i, 0, n) y[i] = lower_bound(ALL(v), y[i]) - v.begin();
	
	FOR(i, 0, n){
		used[i] = 0;
		nused[x[i]][0].insert(i);
		nused[y[i]][1].insert(i);
	}
	FOR(i, 0, n){
		if(used[i])
			continue;
		dfs(i, -1);
	}
	
	if(2 * SZ(ans) != n){
		cout << "No\n";
	}
	else{
		cout << "Yes\n";
		FOR(i, 0, SZ(ans)){
			//assert(x[ans[i].F] == x[ans[i].S] || y[ans[i].F] == y[ans[i].S]);
			 
			cout << ans[i].F + 1 << " " << ans[i].S + 1 << "\n";
		}
	}
	ans.clear();
	FOR(i, 0, n){
		nused[x[i]][0].clear();
		nused[y[i]][1].clear();
		used[i] = 0;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--)
		solve();

	return 0;
}


详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 15828kb

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
1 3
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 487ms
memory: 38192kb

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
99823 99979
99930 99981
99939 99993
99893 99927
99872 99890
99935 99983
99812 99923
99770 99794
99722 99725
99698 99704
99638 99671
99584 99626
99494 99548
99479 99485
99413 99464
99398 99410
99383 99392
99374 99377
99266 99329
99230 99248
99125 99215
99077 99092
99041 99059
99023 99026
98966 98...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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
7 8
5 6
3 4
1 2
27 28
25 26
23 24
21 22
19 20
17 18
15 16
13 14
11 12
9 10
33 34
31 32
29 30
37 38
35 36
57 58
55 56
53 54
51 52
49 50
47 48
45 46
43 44
41 42
39 40
67 68
65 66
63 64
61 62
59 60
73 74
71 72
69 70
99 100
97 98
95 96
93 94
91 92
89 90
87 88
85 86
83 84
81 82
79 80
77 78
75 76
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 326ms
memory: 27824kb

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 837ms
memory: 34292kb

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
99438 99509
89492 99574
82608 85048
92652 97510
88495 89905
78226 78629
61827 64315
94056 95227
58552 59227
92602 95172
87927 88726
85123 85436
88825 98959
85966 88659
82426 84374
79221 81195
72039 75869
70397 70561
51532 63374
99488 99601
98732 98890
96424 97093
92713 93146
90576 94256
84380 87...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 286ms
memory: 16544kb

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

result:

ok 1000 Cases (1000 test cases)