QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#150142#5423. Perfect MatchingrgnerdplayerAC ✓538ms17952kbC++202.6kb2023-08-25 15:22:112023-08-25 15:22:15

Judging History

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

  • [2023-08-25 15:22:15]
  • 评测
  • 测评结果:AC
  • 用时:538ms
  • 内存:17952kb
  • [2023-08-25 15:22:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

template <typename T, class F = less<T>>
struct Discrete {
    vector<T> a;
    Discrete(const vector<T> &v) : a(v) {
        sort(a.begin(), a.end(), F());
        a.erase(unique(a.begin(), a.end()), a.end());
    }
    int size() { return a.size(); }
    int operator()(T x) { return lower_bound(a.begin(), a.end(), x, F()) - a.begin(); }
    T operator[](int i) { return a[i]; }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t;
    cin >> t;

    auto solve = [&]() {
        int n;
        cin >> n;

        vector<int> a(n), x(n), y(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
            x[i] = i - a[i];
            y[i] = i + a[i];
        }

        Discrete dx(x), dy(y);

        vector<vector<pair<int, int>>> g(2 * n);

        for (int i = 0; i < n; i++) {
            x[i] = dx(x[i]), y[i] = dy(y[i]);
            g[x[i]].emplace_back(y[i] + n, i);
            g[y[i] + n].emplace_back(x[i], i);
        }

        vector<int> vis(2 * n), dep(2 * n);
        vector<pair<int, int>> ans;

        auto dfs = [&](auto dfs, int u, int pv, int pe) -> int {
            dep[u] = pv == -1 ? 0 : dep[pv] + 1;
            vis[u] = true;
            vector<int> e;
            for (auto [v, i] : g[u]) {
                if (v == pv) {
                    continue;
                }
                if (vis[v] && dep[v] < dep[u]) {
                    e.push_back(i);
                }
                if (!vis[v] && dfs(dfs, v, u, i)) {
                    e.push_back(i);
                }
            }
            while (int(e.size()) >= 2) {
                ans.emplace_back(e.back(), e.end()[-2]);
                e.pop_back();
                e.pop_back();
            }
            if (!e.empty() && pe != -1) {
                ans.emplace_back(e[0], pe);
                return false;
            } else {
                return true;
            }
        };

        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                dfs(dfs, i, -1, -1);
            }
        }

        if (int(ans.size()) != n / 2) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
            for (auto [x, y] : ans) {
                cout << x + 1 << ' ' << y + 1 << '\n';
            }
        }
    };
    
    while (t--) {
        solve();
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3800kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 296ms
memory: 16268kb

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
78 77
138 137
201 200
242 244
287 289
309 308
315 314
321 320
335 337
380 382
396 395
450 449
459 458
462 461
480 479
515 517
518 520
524 526
554 556
567 566
617 619
660 659
734 736
761 763
788 790
851 853
903 902
933 932
978 977
987 986
1089 1088
1104 1103
1160 1162
1218 1217
1271 1273
12...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3600kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 249ms
memory: 17264kb

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
49560 49559
29398 29397
29396 29395
29394 29393
29392 29391
29390 29389
29388 29387
29386 29385
29384 29383
29382 29381
29380 29379
29378 29377
29376 29375
29374 29373
29372 29371
29370 29369
29368 29367
29366 29365
29364 29363
29362 29361
29360 29359
29358 29357
29356 29355
29354 29353
34124 34...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 538ms
memory: 17952kb

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 26518
8564 1121
36811 36817
95315 8931
96991 61541
81303 70110
16772 13611
34736 778
88310 80993
74032 11544
821 940
80608 33052
9050 10585
78597 37367
84943 65442
41232 50244
91157 52881
10333 5417
18933 19162
97729 87006
59542 3408
79681 23980
67617 66364
27149 10211
57643 44140...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 196ms
memory: 3940kb

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
14 15
57 59
66 67
77 78
98 99
130 129
142 144
161 162
165 167
183 185
184 186
198 199
200 202
205 207
214 215
232 233
243 245
271 270
279 280
284 286
307 308
312 314
315 316
320 321
328 330
333 332
370 372
384 385
387 388
412 413
422 421
424 426
427 428
432 433
435 436
440 442
...

result:

ok 1000 Cases (1000 test cases)