QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#223661#5423. Perfect MatchingluanmengleiRE 258ms23168kbC++172.2kb2023-10-22 14:59:342023-10-22 14:59:34

Judging History

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

  • [2023-10-22 14:59:34]
  • 评测
  • 测评结果:RE
  • 用时:258ms
  • 内存:23168kb
  • [2023-10-22 14:59:34]
  • 提交

answer

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

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

#define PASSED debug("PASSED (%s) LINE #%s", __FUNCTION__, __LINE__)

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> void chkmax(T &x, L y) { if (x < y) x = y; }
template <typename T, typename L> void chkmin(T &x, L y) { if (x > y) x = y; }

const int N = 1e5 + 10;
int n, a[N], b[N * 2], cnt, tot, bel[N];
bool vis[N * 2], used[N];
bool GG;
vector<pair<int, int>> G[N * 2], ans;

void dfs(int x, int fa) {
	vis[x] = true;
	for (auto [y, _] : G[x]) if (!vis[y])
		dfs(y, x);
	vector<int> avail;
	for (auto [y, id] : G[x]) if (!used[id] && y != fa)
		avail.push_back(id);
	
	if (avail.size() % 2) {
		if (fa == 0) {
			GG = true;
			return;
		}
		for (auto [y, id] : G[x]) if (y == fa)
			avail.push_back(id);
	}
	for (int i = 0; i < (int) avail.size(); i += 2) {
		int u = avail[i], v = avail[i + 1];
		used[u] = used[v] = true;
		ans.push_back({ bel[u], bel[v] });
	}
}

void solve() {
	// debug("run new solve");
	GG = false;
	tot = cnt = 0;
	ans.clear();

	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		b[++ cnt] = a[i] - i, b[++ cnt] = a[i] + i;
	}
	sort(b + 1, b + 1 + cnt);
	cnt = unique(b + 1, b + 1 + cnt) - b - 1;
	for (int i = 1; i <= 2 * cnt; i ++)
		G[i].clear(), vis[i] = false;
	for (int i = 1; i <= n; i ++) {
		int x = lower_bound(b + 1, b + 1 + cnt, a[i] - i) - b;
		int y = lower_bound(b + 1, b + 1 + cnt, a[i] + i) - b + cnt;
		// debug("x: %d y: %d", x, y);
		used[++ tot] = false, bel[tot] = i;
		G[x].emplace_back(y, tot);
		G[y].emplace_back(x, tot);
	}
	for (int i = 1; i <= cnt; i ++) if (!vis[i] && !GG) {
		dfs(i, 0);
	}
	if (GG) {
		cout << "No\n";
	} else {
		cout << "Yes\n";
		for (auto [x, y] : ans)
			cout << x << " " << y << "\n";
	}
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int tt; cin >> tt;
	while (tt --)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 258ms
memory: 23168kb

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: 2ms
memory: 9480kb

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: -100
Runtime Error

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:


result: