QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125200#5423. Perfect MatchingsavacskaAC ✓1606ms57368kbC++232.7kb2023-07-16 05:24:532023-07-16 05:24:55

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-16 05:24:55]
  • 评测
  • 测评结果:AC
  • 用时:1606ms
  • 内存:57368kb
  • [2023-07-16 05:24:53]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;

int mas[100005];
map <int, int> opa_plus, opa_minus;
int num_plus[100005], num_minus[100005];
vector <pair <int, int> > g[200005];
bool used[200005];
int sz[200005];

set <int> two_times[200005], one_times[200005];

void dfs(int v, int &kol)
{
	used[v] = true;
	kol += sz[v];
	for (const auto &[u, num] : g[v])
		if (!used[u])
			dfs(u, kol);
	return; 	
}

void build_ans(int v, int pr)
{
 	used[v] = true;
 	for (const auto &[u, num] : g[v])
 		if (!used[u])
 			build_ans(u, num);
 	
 	int kol = (int) one_times[v].size() + (int) two_times[v].size();

 	vector <int> spis;
   	for (int x : one_times[v]) spis.pb(x);
   	one_times[v].clear();
   	for (int x : two_times[v])
   	{
   		if (kol % 2 == 0 || x != pr) spis.pb(x);
   		int sec = num_plus[x] ^ num_minus[x] ^ v;
   		two_times[sec].erase(x); 	
   	}
   	two_times[v].clear();
   	if (kol % 2 == 1) one_times[num_plus[pr] ^ num_minus[pr] ^ v].insert(pr);

   	for (int i = 0; i < (int) spis.size(); i += 2) cout << spis[i] << ' ' << spis[i + 1] << '\n';
   	return;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);

 	int test;
 	cin >> test;
 	for (int rep = 1; rep <= test; rep++)
 	{
 	 	int n;
 	 	cin >> n;
 	 	for (int i = 1; i <= n; i++) cin >> mas[i];

 	 	opa_plus.clear(), opa_minus.clear();

 	 	for (int i = 1; i <= n; i++)
 	 	{
 	 		opa_plus.insert(mp(mas[i] + i, 0));
 	 		opa_minus.insert(mp(mas[i] - i, 0)); 	
 	 	}

 	 	int cnt = 0;
 	 	for (auto &[dd, num] : opa_plus)
 	 		num = ++cnt;
 	 	for (auto &[dd, num] : opa_minus)
 	 		num = ++cnt;

 	 	for (int i = 1; i <= cnt; i++) g[i].clear(), sz[i] = 0, one_times[i].clear(), two_times[i].clear();
 	 	for (int i = 1; i <= n; i++)
 	 	{
 	 	 	num_plus[i] = opa_plus[mas[i] + i];
 	 	 	num_minus[i] = opa_minus[mas[i] - i];
 	 	 	g[num_plus[i]].pb(mp(num_minus[i], i));
 	 	 	g[num_minus[i]].pb(mp(num_plus[i], i));
 	 	 	sz[num_plus[i]]++, sz[num_minus[i]]++;
 	 	 	two_times[num_plus[i]].insert(i);
 	 	 	two_times[num_minus[i]].insert(i);
 	 	}

 	 	bool fl = true;
 	 	for (int i = 1; i <= cnt; i++) used[i] = false;
 	 	for (int i = 1; i <= cnt; i++)
 	 	{
 	 	 	if (!used[i])
 	 	 	{
 	 	 	 	int kol = 0;
 	 	 	 	dfs(i, kol);
 	 	 	 	if (kol / 2 % 2 == 1) fl = false;
 	 	 	}
 	 	}
 	 	if (!fl) {cout << "No\n"; continue;}

 	 	cout << "Yes\n";
 	 	for (int i = 1; i <= cnt; i++) used[i] = false;
 	 	for (int i = 1; i <= cnt; i++)
 	 	{
 	 	 	if (!used[i]) build_ans(i, -1);
 	 	}
 	}

 	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 28480kb

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 1008ms
memory: 49752kb

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
77 78
137 138
200 201
242 244
287 289
308 309
314 315
320 321
335 337
380 382
395 396
449 450
458 459
461 462
479 480
515 517
518 520
524 526
554 556
566 567
617 619
659 660
734 736
761 763
788 790
851 853
902 903
932 933
977 978
986 987
1088 1089
1103 1104
1160 1162
1217 1218
1271 1273
1283 128...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
58 39
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
36 37
38 35
2 3
4 5
6 7
8 1
69 70
71 72
73 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 617ms
memory: 57368kb

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 1606ms
memory: 50760kb

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
89504 28
8564 26518
63463 1121
36811 36817
8931 95315
96991 61541
81132 92548
41302 83637
34736 778
12537 4360
99552 2005
97953 92893
58176 30631
70597 19622
37677 26691
27149 66364
67617 10211
17075 44140
57643 11472
23176 35741
95323 12598
9050 10585
68565 28519
21782 10746
47710 63141
1793 55...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 390ms
memory: 28472kb

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
22 23
33 34
47 48
72 73
107 108
127 128
147 148
155 156
179 180
192 193
210 211
260 261
262 263
309 310
318 319
342 343
404 405
406 407
417 418
443 444
455 456
502 503
583 584
599 600
663 664
699 700
704 705
718 719
720 721
727 728
739 740
770 771
857 858
912 913
951 952
962 96...

result:

ok 1000 Cases (1000 test cases)