QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#77818#5423. Perfect MatchingAPJifengcAC ✓530ms25224kbC++142.3kb2023-02-15 17:35:192023-02-15 17:35:21

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-15 17:35:21]
  • 评测
  • 测评结果:AC
  • 用时:530ms
  • 内存:25224kb
  • [2023-02-15 17:35:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int a[MAXN], n;
vector<int> val1, val2;
vector<pair<int, int>> e[MAXN];
void add(int a, int b, int i) {
    e[a].push_back({b, i});
    e[b].push_back({a, i});
}
int u[MAXN], v[MAXN];
bool vis[MAXN];
bool used[MAXN];
vector<pair<int, int>> ans;
void dfs(int u, int pre) {
    vis[u] = 1;
    int lst = 0;
    for (auto p : e[u]) if (p.second != pre) {
        int v = p.first;
        int w = p.second;
        if (!vis[v]) dfs(v, w);
        if (!used[w]) {
            if (lst) {
                ans.push_back({lst, w});
                used[lst] = used[w] = 1;
                lst = 0;
            } else {
                lst = w;
            }
        }
    }
    if (lst && pre) {
        ans.push_back({lst, pre});
        used[lst] = used[pre] = 1;
    }
}
int T;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (n & 1) {
            printf("No\n");
            continue;
        }
        val1.clear(), val2.clear();
        ans.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            val1.push_back({a[i] - i});
            val2.push_back({a[i] + i});
        }
        sort(val1.begin(), val1.end());
        sort(val2.begin(), val2.end());
        val1.erase(unique(val1.begin(), val1.end()), val1.end());
        val2.erase(unique(val2.begin(), val2.end()), val2.end());
        int m = val1.size() + val2.size();
        for (int i = 1; i <= n; i++) {
            used[i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            vis[i] = 0;
            e[i].clear();
        }
        for (int i = 1; i <= n; i++) {
            int u = lower_bound(val1.begin(), val1.end(), a[i] - i) - val1.begin() + 1;
            int v = lower_bound(val2.begin(), val2.end(), a[i] + i) - val2.begin() + 1;
            v += val1.size();
            add(u, v, i);
        }
        for (int i = 1; i <= m; i++) if (!vis[i]) {
            dfs(i, 0);
        }
        if (ans.size() == n / 2) {
            printf("Yes\n");
            for (auto p : ans) {
                printf("%d %d\n", p.first, p.second);
            }
        } else {
            printf("No\n");
        }
    }
    return 0;
}

/*
6
14 22 33 11 25 36

*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9720kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
1 4
2 5
3 6
Yes
2 4
1 3
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 299ms
memory: 23548kb

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
14 15
16 20
77 78
3 79
137 138
200 201
139 202
242 244
287 289
308 309
314 315
310 316
320 321
335 337
380 382
395 396
322 397
449 450
458 459
451 460
461 462
479 480
463 481
515 517
518 520
524 526
554 556
566 567
617 619
659 660
568 661
734 736
761 763
788 790
851 853
902 903
932 933
904 934
9...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 8644kb

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
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
29 30
31 32
33 34
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
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
59 60
61 62
63 64
65 66
67 68
35 36
37 38
1 2
3 4
5 6
7 8
69 70
71 72
73 74
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 270ms
memory: 25224kb

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
29329 29330
29331 29332
29333 29334
29335 29336
29337 29338
29339 29340
29341 29342
29343 29344
29345 29346
29347 29348
29349 29350
29351 29352
71753 71754
71755 71756
71757 71758
71759 71760
71761 71762
71763 71764
71765 71766
71767 71768
71769 71770
71771 71772
71773 71774
71775 71776
71777 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 530ms
memory: 18896kb

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
8564 26518
63463 1121
57 58
49 54
36811 36817
84 129
8931 95315
506 7625
55 73
13 14
89504 28
153 222
711 797
47 48
99 152
70110 81303
13611 16772
126 132
34736 778
62 7528
128 159
109 193
859 1003
92 127
435 443
80784 80963
821 11544
88310 80993
74032 940
33052 80608
188 559
155 164
3199 1661
4...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 234ms
memory: 8632kb

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
15 14
20 24
3 5
26 28
29 38
41 43
45 49
59 57
68 70
75 74
71 83
113 112
87 118
119 122
124 126
130 131
129 134
139 141
144 142
143 146
152 151
167 165
171 170
175 177
185 183
186 184
202 200
178 203
207 205
213 212
208 219
221 220
245 243
226 257
267 266
271 272
268 270
273 274...

result:

ok 1000 Cases (1000 test cases)