QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73624 | #5423. Perfect Matching | hos_lyric | AC ✓ | 571ms | 17528kb | C++14 | 3.2kb | 2023-01-26 19:24:05 | 2023-01-26 19:24:07 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
int M;
vector<Int> Y;
int N;
vector<int> A, B;
vector<vector<int>> G;
vector<int> vis;
vector<int> used;
vector<pair<int, int>> ans;
int dfs(int u, int pi) {
vis[u] = 1;
int ret = -1;
for (const int i : G[u]) if (!used[i]) {
used[i] = 1;
const int v = A[i] ^ B[i] ^ u;
int res = -1;
if (!vis[v]) {
res = dfs(v, i);
}
if (~res) {
ans.emplace_back(i, res);
} else {
if (~ret) {
ans.emplace_back(ret, i);
ret = -1;
} else {
ret = i;
}
}
}
return ret;
}
int main() {
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
scanf("%d", &M);
Y.resize(M);
for (int i = 0; i < M; ++i) {
scanf("%lld", &Y[i]);
}
vector<Int> ps(M), qs(M);
for (int i = 0; i < M; ++i) {
ps[i] = Y[i] + i;
qs[i] = Y[i] - i;
}
sort(ps.begin(), ps.end());
sort(qs.begin(), qs.end());
ps.erase(unique(ps.begin(), ps.end()), ps.end());
qs.erase(unique(qs.begin(), qs.end()), qs.end());
const int psLen = ps.size();
const int qsLen = qs.size();
N = psLen + qsLen;
A.resize(M);
B.resize(M);
for (int i = 0; i < M; ++i) {
A[i] = lower_bound(ps.begin(), ps.end(), Y[i] + i) - ps.begin();
B[i] = lower_bound(qs.begin(), qs.end(), Y[i] - i) - qs.begin();
B[i] += psLen;
}
// cerr<<"A = "<<A<<", B = "<<B<<endl;
G.assign(N, {});
for (int i = 0; i < M; ++i) {
G[A[i]].push_back(i);
G[B[i]].push_back(i);
}
vis.assign(N, 0);
used.assign(M, 0);
ans.clear();
for (int u = 0; u < N; ++u) if (!vis[u]) {
const int res = dfs(u, 0);
if (~res) {
goto failed;
}
}
puts("Yes");
for (const auto &p : ans) {
printf("%d %d\n", p.first + 1, p.second + 1);
}
assert(2 * (int)ans.size() == M);
continue;
failed:{}
puts("No");
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3612kb
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: 318ms
memory: 14188kb
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 14 15 16 20 77 78 3 79 137 138 200 201 139 202 244 242 289 287 308 309 314 315 310 316 320 321 337 335 382 380 395 396 322 397 449 450 458 459 451 460 461 462 479 480 463 481 517 515 520 518 526 524 556 554 566 567 619 617 659 660 568 661 736 734 763 761 790 788 853 851 902 903 932 933 904 934 9...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 3636kb
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 39 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 36 37 35 38 2 3 4 5 6 7 1 8 69 70 71 72 73 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 283ms
memory: 17528kb
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: 571ms
memory: 15436kb
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 47 48 13 14 28 89504 49 54 57 58 8564 26518 1121 63463 153 222 36817 36811 84 129 8931 95315 506 7625 536 1600 61541 96991 126 132 14495 23105 33602 36346 99 152 107 243 81132 92548 8961 29263 41302 83637 11086 16914 62 7528 859 1003 92 127 513 768 66 118 288 2392 778 34736 4360 12537 542 664 20...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 209ms
memory: 3780kb
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 4 11 6 9 16 17 18 21 22 23 25 27 31 32 33 34 35 42 47 48 51 62 72 73 64 79 82 86 90 96 101 103 107 108 109 111 127 128 121 145 147 148 155 156 157 159 164 166 169 174 179 180 176 191 192 193 195 201 210 211 204 223 229 230 237 244 246 252 260 261 262 263 269 276 282 292 293 294...
result:
ok 1000 Cases (1000 test cases)