QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#223657 | #5423. Perfect Matching | luanmenglei | RE | 271ms | 23008kb | C++17 | 2.4kb | 2023-10-22 14:57:47 | 2023-10-22 14:57:48 |
Judging History
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, ecnt, bel[N];
bool vis[N * 2], used[N];
bool GG;
vector<pair<int, int>> G[N * 2], ans;
void dfs(int x, int fa) {
// debug("%d => %d", fa, x);
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);
// debug("x: %d size: %llu", x, avail.size());
if (avail.size() % 2) {
if (fa == 0) {
GG = true;
return;
}
for (auto [y, id] : G[x]) if (y == fa)
assert(!used[id]), avail.push_back(id);
}
// debug("x: %d size: %llu", x, avail.size());
assert(avail.size() % 2 == 0);
for (int i = 0; i < (int) avail.size(); i += 2) {
int u = avail[i], v = avail[i + 1];
// debug("used %d %d", u, v);
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: 2ms
memory: 8840kb
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: 271ms
memory: 23008kb
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: 9904kb
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 ...