QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#74424#5423. Perfect Matchingmagicduck#WA 478ms29016kbC++142.1kb2023-02-01 16:41:112023-02-01 16:41:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-01 16:41:12]
  • 评测
  • 测评结果:WA
  • 用时:478ms
  • 内存:29016kb
  • [2023-02-01 16:41:11]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)