QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74424 | #5423. Perfect Matching | magicduck# | WA | 478ms | 29016kb | C++14 | 2.1kb | 2023-02-01 16:41:11 | 2023-02-01 16:41: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 = v - i, y = 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;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 19584kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 3 6 2 5 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 478ms
memory: 29016kb
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 22 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 12...
result:
wrong answer abs(283-317) != abs(a[283]-a[317]) (test case 1)