QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#74540#5423. Perfect MatchingmagicduckAC ✓1201ms39860kbC++142.1kb2023-02-02 12:45:192023-02-02 12:45:20

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:45:20]
  • 评测
  • 测评结果:AC
  • 用时:1201ms
  • 内存:39860kb
  • [2023-02-02 12:45:19]
  • 提交

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> A, B; int tot = 0;
        for(int i = 1; i <= n; i++) {
            int v; read(v);
            const int x = v - i, y = v + i;
            if(!A[x]) A[x] = ++tot;
            if(!B[y]) B[y] = ++tot;
            edge[A[x]].emplace_back(B[y], i);
            edge[B[y]].emplace_back(A[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: 3ms
memory: 19764kb

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: 0
Accepted
time: 452ms
memory: 29624kb

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:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 2ms
memory: 20856kb

input:

10
100
28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...

output:

Yes
1 2
3 4
5 6
7 8
28 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 9
34 30
31 32
33 29
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
68 60
61 62
63 64
65 66
67 59
74 70
71 72
73 69
100 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 75
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 523ms
memory: 39860kb

input:

10
100000
-40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...

output:

Yes
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100
101 ...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 1201ms
memory: 31508kb

input:

10
100000
0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...

output:

Yes
89504 28
63463 8564
26518 1121
36811 36817
95315 8931
96991 61541
81303 70110
16772 13611
34736 778
88310 80993
821 11544
74032 940
80608 33052
9050 10585
78597 37367
41232 84943
65442 50244
91157 52881
5417 10333
18933 19162
97729 3408
59542 87006
79681 23980
67617 27149
66364 10211
57643 17075...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 238ms
memory: 20644kb

input:

1000
1000
-2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...

output:

No
No
No
No
No
No
Yes
23 22
34 33
48 47
73 72
108 107
128 127
148 147
156 155
180 179
193 192
211 210
261 260
263 262
310 309
319 318
343 342
405 404
407 406
418 417
444 443
456 455
503 502
584 583
600 599
664 663
700 699
705 704
719 718
721 720
728 727
740 739
771 770
858 857
913 912
952 951
963 96...

result:

ok 1000 Cases (1000 test cases)