QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#74539 | #5423. Perfect Matching | magicduck | WA | 459ms | 29260kb | C++14 | 2.1kb | 2023-02-02 12:43:11 | 2023-02-02 12:43:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
int R = 1; F = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
F *= R;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 5e5 + 10;
vector<pair<int, int> > edge[N], R; int n, vis[N], flag[N], f[N];
void dfs(int x) {
//cout << x << endl;
vis[x] = 1;
for(auto i : edge[x]) {
if(vis[i.first]) continue;
f[i.first] = i.second; dfs(i.first);
}
}
void calc(int x) {
for(auto i : edge[x])
if(f[i.first] == i.second) calc(i.first);
for(auto &i : edge[x])
if(i.second == f[x]) swap(i, edge[x].back());
int l = 0;
for(auto i : edge[x]) {
if(flag[i.second]) continue;
if(l) R.emplace_back(l, i.second), flag[l] = flag[i.second] = 1, l = 0;
else l = i.second;
}
}
int main() {
//file("");
int T; read(T);
while(T--) {
read(n); R.clear();
for(int i = 1; i <= n * 4; i++) vis[i] = flag[i] = f[i] = 0, edge[i].clear();
map<int, int> M; int tot = 0;
for(int i = 1; i <= n; i++) {
int v; read(v);
const int x = i - v, y = n + v + i;
if(!M[x]) M[x] = ++tot;
if(!M[y]) M[y] = ++tot;
edge[M[x]].emplace_back(M[y], i);
edge[M[y]].emplace_back(M[x], i);
}
int ans = 1;
for(int i = 1; i <= tot && ans; i++)
if(!vis[i]) {
dfs(i), calc(i);
for(auto j : edge[i])
if(!flag[j.second]) ans = 0;
}
if(!ans) {
puts("No"); continue;
}
puts("Yes");
for(auto i : R) cout << i.first << ' ' << i.second << '\n';
}
#ifdef _MagicDuck
fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 18844kb
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 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 459ms
memory: 29260kb
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 21 50021 77 78 137 138 200 201 53 55 84 83 91 90 127 126 11 12 5 7 29 30 98 99 122 123 128 129 203 205 224 225 290 291 362 364 371 372 377 378 389 391 416 417 434 435 509 511 584 586 656 658 665 666 752 753 770 771 806 808 821 822 824 826 872 873 923 925 962 963 968 970 1001 1002 1007 1008 1025 ...
result:
wrong answer abs(21-50021) != abs(a[21]-a[50021]) (test case 1)