QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#74539#5423. Perfect MatchingmagicduckWA 459ms29260kbC++142.1kb2023-02-02 12:43:112023-02-02 12:43: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-02 12:43:12]
  • 评测
  • 测评结果:WA
  • 用时:459ms
  • 内存:29260kb
  • [2023-02-02 12:43: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 = 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)