QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#230625 | #5423. Perfect Matching | MyCall | WA | 159ms | 34660kb | C++14 | 3.0kb | 2023-10-28 19:53:28 | 2023-10-28 19:53:30 |
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 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)
if ((!i.first->Vis)) {
Cur = i.second;
if (i.first->DFS(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() {
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10680kb
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: -100
Wrong Answer
time: 159ms
memory: 34660kb
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:
No No No No No No No No No No
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)