QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#790274#5423. Perfect MatchingvwxyzAC ✓819ms25696kbC++233.2kb2024-11-28 09:31:142024-11-28 09:31:15

Judging History

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

  • [2024-11-28 09:31:15]
  • 评测
  • 测评结果:AC
  • 用时:819ms
  • 内存:25696kb
  • [2024-11-28 09:31:14]
  • 提交

answer

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;

pair<map<long long, int>, vector<long long>> Compress(const vector<long long>& lst) {
    vector<long long> decomp(lst.begin(), lst.end());
    sort(decomp.begin(), decomp.end());
    decomp.erase(unique(decomp.begin(), decomp.end()), decomp.end());
    map<long long, int> comp;
    for (int i = 0; i < decomp.size(); ++i) {
        comp[decomp[i]] = i;
    }
    return {comp, decomp};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<long long> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }

        const long long INF = 1LL << 60;
        vector<long long> to_compress;
        for (int i = 0; i < N; ++i) {
            to_compress.push_back(A[i] + i);
            to_compress.push_back(A[i] - i + INF);
        }

        auto [comp, decomp] = Compress(to_compress);
        int le = comp.size();
        vector<vector<pair<int, int>>> graph(le);

        for (int n = 0; n < N; ++n) {
            int i = comp[A[n] + n];
            int j = comp[A[n] - n + INF];
            graph[i].emplace_back(j, n);
            graph[j].emplace_back(i, n);
        }

        vector<int> tour;
        vector<bool> seen(le, false);
        vector<int> parents(le, -1);
        for (int x = 0; x < le; ++x) {
            if (seen[x]) continue;
            queue<int> q;
            q.push(x);
            seen[x] = true;
            while (!q.empty()) {
                int current = q.front();
                q.pop();
                tour.push_back(current);
                for (auto& [y, n] : graph[current]) {
                    if (!seen[y]) {
                        parents[y] = current;
                        seen[y] = true;
                        q.push(y);
                    }
                }
            }
        }

        reverse(tour.begin(), tour.end());
        vector<vector<int>> dp(le);
        vector<pair<int, int>> ans_lst;
        vector<bool> seen_nodes(N, false);

        for (int x : tour) {
            for (auto& [y, n] : graph[x]) {
                if (y == parents[x]) continue;
                if (parents[y] == x && !dp[y].empty()) {
                    ans_lst.emplace_back(n, dp[y].back());
                    dp[y].pop_back();
                } else if (!seen_nodes[n]) {
                    dp[x].push_back(n);
                    seen_nodes[n] = true;
                }
            }
            while (dp[x].size() >= 2) {
                int a = dp[x].back(); dp[x].pop_back();
                int b = dp[x].back(); dp[x].pop_back();
                ans_lst.emplace_back(a, b);
            }
        }

        if ((int)ans_lst.size() * 2 == N) {
            cout << "Yes\n";
            for (auto& [i, j] : ans_lst) {
                cout << i + 1 << " " << j + 1 << "\n";
                assert(abs(i - j) == abs(A[i] - A[j]));
            }
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 435ms
memory: 20212kb

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
99983 99935
99923 99869
99812 99794
99770 99725
99722 99704
99698 99671
99638 99626
99584 99548
99494 99485
99479 99464
99413 99410
99398 99392
99383 99377
99374 99329
99266 99248
99230 99215
99125 99092
99077 99059
99041 99026
99023 98978
98966 98951
98945 98918
98894 98891
98858 98837
98807 98...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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
1 2
38 37
35 36
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
39 40
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 460ms
memory: 25696kb

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
49559 49560
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
29353 29354
34124 34...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 819ms
memory: 20984kb

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
55183 37843
74887 78391
81303 70110
97255 65286
82489 94299
15153 78548
92669 15078
89506 79567
85036 34586
63078 56160
58066 67820
89848 84747
35744 34651
76008 75518
58415 80843
78656 60176
84286 74114
85980 64483
59770 20885
93142 89017
97731 91507
88950 59746
70989 92244
24826 72626
38593 89...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 328ms
memory: 3872kb

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
1000 995
993 979
978 960
955 934
919 908
907 895
891 890
884 867
864 863
850 839
835 834
831 829
827 825
824 822
820 807
806 800
789 764
753 746
736 709
698 697
690 688
687 683
682 677
671 669
668 661
656 648
626 615
608 606
601 585
579 578
561 557
535 513
510 507
500 499
490 4...

result:

ok 1000 Cases (1000 test cases)