QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648302#5423. Perfect Matching0x3fffffffAC ✓515ms16952kbC++202.3kb2024-10-17 18:12:352024-10-17 18:12:37

Judging History

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

  • [2024-10-17 18:12:37]
  • 评测
  • 测评结果:AC
  • 用时:515ms
  • 内存:16952kb
  • [2024-10-17 18:12:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

void solve() {
    int n; cin >> n;
    vector<int>a(n + 1);
    vector<int>v1,v2;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v1.push_back(i - a[i]);
        v2.push_back(i + a[i]);
    }

    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    int m1 = v1.size();
    int m2 = v2.size();
    // for(auto x:v1){
        // cout<<x<<" ";
    // }
    // cout<<"\n";

    int m=m1+m2;
    vector<vector<int>>h(m + 10);
    vector<array<int, 2>>e;
    vector<int>vis(m + 10), hav(m + 10), pp(m * 4 + 10, 1);

    auto add = [&](int a, int b) {
        // cout<<a<<" "<<b<<"\n";
        h[a].push_back(e.size());
        e.push_back({a, b});
    };

    for (int i = 1; i <= n; i++) {
        int x = lower_bound(v1.begin(), v1.end(), i - a[i]) - v1.begin() + 1;
        int y = lower_bound(v2.begin(), v2.end(), i + a[i]) - v2.begin() + 1;
        // cout<<x<<" "<<y<<"\n";
        add(x, y+m1);
        add(y+m1, x);
    }
    vector<array<int, 2>>ans;
    auto dfs = [&](auto && ff, int u, int lst)->void{
        vis[u] = 1;
        for (int i : h[u]) {
            int v = e[i][1];
            int ok = pp[i];
            pp[i] = pp[i ^ 1] = 0;
            if (ok) {
                if (!vis[v] and i != (lst ^ 1)) {
                    ff(ff, v, 0);
                }
                if (hav[v]) {
                    ans.push_back({hav[v], i / 2 + 1});
                    hav[v] = 0;
                } else if (hav[u] ) {
                    ans.push_back({hav[u], i / 2 + 1});
                    hav[u] = 0;
                } else {
                    hav[u] = i / 2 + 1;
                }
            }
        }
    };
    for (int i = 1; i <=m; i++) {
        if (!vis[i])dfs(dfs, i, -1);
    }
    // cout<<ans.size()<<"\n";
    if ((int)ans.size() == 0 || (int)ans.size() * 2 != n) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    for (auto [u, v] : ans) {
        cout << u << " " << v << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 256ms
memory: 14204kb

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
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
977 978...

result:

ok 10 Cases (10 test cases)

Test #3:

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

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 226ms
memory: 16952kb

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 515ms
memory: 15896kb

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
13 14
89504 28
6 29
49 54
4 15
57 58
8564 26518
63463 1121
61 522
153 222
36811 36817
84 129
8931 95315
506 7625
42 87
536 1600
96991 61541
47 48
99 152
25 124
70110 81303
13611 16772
7 323
126 132
34736 778
62 7528
52 1672
859 1003
92 127
262 768
66 118
50 1549
8 476
288 2392
51 454
317 332
122...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 190ms
memory: 3760kb

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
3 5
26 28
2 10
14 15
19 44
29 57
52 59
60 63
66 67
77 78
80 84
95 97
98 99
100 115
129 130
117 131
142 144
161 162
165 167
140 168
183 185
184 186
189 196
198 199
200 202
197 206
205 207
214 215
209 216
217 218
232 233
234 238
243 245
239 247
248 253
258 264
270 271
265 272
279...

result:

ok 1000 Cases (1000 test cases)