QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#230634 | #5423. Perfect Matching | MyCall | AC ✓ | 380ms | 36296kb | C++14 | 3.1kb | 2023-10-28 19:58:29 | 2023-10-28 19:58:29 |
Judging History
answer
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
#define Wild_Donkey 0
#define foreplay for
#define wild while
using namespace std;
inline unsigned RD() {
unsigned intmp(0);
char rdch(getchar());
while (rdch < '0' || rdch > '9') rdch = getchar();
while (rdch >= '0' && rdch <= '9')
intmp = (intmp << 3) + (intmp << 1) + rdch - '0', rdch = getchar();
return intmp;
}
inline int RDsg() {
int rdtp(0), rdsg(1);
char rdch(getchar());
while ((rdch < '0' || rdch > '9') && (rdch != '-')) rdch = getchar();
if (rdch == '-') rdsg = -1, rdch = getchar();
while (rdch >= '0' && rdch <= '9')
rdtp = (rdtp << 3) + (rdtp << 1) + rdch - '0', rdch = getchar();
return rdtp * rdsg;
}
unsigned a[100005], b[100005], c[100005];
unsigned n, na, nb, A, B, t;
unsigned Cnt(0), Ans[50005][2];
char EdV[100005], Flg(0);
struct Node {
vector<pair<Node*, unsigned> > Edge;
char Vis;
inline char DFS(unsigned Pre) {
// printf("DFS %u %u\n", Pre, Cnt);
Vis = 1;
unsigned Lst(0), Cur(0);
for (auto i : Edge) {
Cur = i.second;
if (!EdV[Cur]) {
EdV[Cur] = 1;
if ((!i.first->Vis) && (!i.first->DFS(Cur))) Cur = 0;
if (Cur) {
if (Lst)
Ans[++Cnt][0] = Lst, Ans[Cnt][1] = Cur, Lst = 0;
else
Lst = Cur;
}
}
}
// printf("Lst %u\n", Lst);
if (!Lst) return 1;
if (Pre) Ans[++Cnt][0] = Pre, Ans[Cnt][1] = Lst;
return 0;
}
} N[200005];
inline void Clr() {
memset(EdV, 0, n + 2);
for (unsigned i(na + nb); i; --i) N[i].Edge.clear(), N[i].Vis = 0;
n = RD(), Flg = Cnt = na = nb = 0;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
t = RD();
for (unsigned T(1); T <= t; ++T) {
Clr();
for (unsigned i(1); i <= n; ++i) {
A = RDsg() + 1000100000;
a[i] = A - i;
b[i] = A + i;
}
for (unsigned i(1); i <= n; ++i) c[i] = a[i];
sort(c + 1, c + n + 1);
na = unique(c + 1, c + n + 1) - c - 1;
for (unsigned i(1); i <= n; ++i)
a[i] = lower_bound(c + 1, c + na + 1, a[i]) - c;
for (unsigned i(1); i <= n; ++i) c[i] = b[i];
sort(c + 1, c + n + 1);
nb = unique(c + 1, c + n + 1) - c - 1;
for (unsigned i(1); i <= n; ++i)
b[i] = lower_bound(c + 1, c + nb + 1, b[i]) - c;
for (unsigned i(1); i <= n; ++i) {
A = a[i], B = b[i];
N[A].Edge.push_back({N + na + B, i});
N[na + B].Edge.push_back({N + A, i});
}
for (unsigned i(1); i <= na; ++i)
if (!N[i].Vis) Flg |= (!N[i].DFS(0));
if ((Cnt << 1) != n) {
printf("No\n");
} else {
printf("Yes\n");
for (unsigned i(1); i <= Cnt; ++i)
printf("%u %u\n", Ans[i][0], Ans[i][1]);
}
}
// system("pause");
return Wild_Donkey;
}
/*
2
6
1 2 3 4 -3 2
4
1 2 3 0
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 10172kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 2 5 3 6 Yes 2 4 3 1 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 208ms
memory: 35040kb
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: 2ms
memory: 10076kb
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 34 33 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 100 99 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 27 59 60 61 62 63 64 65 66 68 67 35 36 37 38 1 2 3 4 5 6 7 8 69 70 71 72 74 73 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 145ms
memory: 36296kb
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 29352 29351 71753 71754 71755 71756 71757 71758 71759 71760 71761 71762 71763 71764 71765 71766 71767 71768 71769 71770 71771 71772 71773 71774 71775 71776 71777 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 380ms
memory: 24880kb
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 8564 26518 1121 63463 57 58 49 54 36817 36811 84 129 8931 95315 506 7625 55 73 13 14 28 89504 153 222 711 797 47 48 99 152 70110 81303 13611 16772 126 132 778 34736 62 7528 128 159 109 193 859 1003 92 127 435 443 80963 80784 821 11544 80993 88310 940 74032 33052 80608 188 559 155 164 1661 3199 3...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 118ms
memory: 11724kb
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 14 15 20 24 3 5 26 28 29 38 41 43 45 49 57 59 68 70 74 75 71 83 112 113 87 118 119 122 124 126 130 131 129 134 139 141 142 144 143 146 151 152 165 167 170 171 175 177 183 185 184 186 200 202 178 203 205 207 212 213 208 219 220 221 243 245 226 257 266 267 271 272 268 270 273 274...
result:
ok 1000 Cases (1000 test cases)