QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186130#5423. Perfect Matching_LAP_AC ✓552ms124080kbC++142.4kb2023-09-23 08:54:562023-09-23 08:54:58

Judging History

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

  • [2023-09-23 08:54:58]
  • 评测
  • 测评结果:AC
  • 用时:552ms
  • 内存:124080kb
  • [2023-09-23 08:54:56]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, A[N]; vector<int> E[N]; vector<pair<int, int>> G[N];
vector<long long> lsh; vector<pair<int, int>> ans;
bool vis[N], used[N];

int dep[N], fa[N]; vector<int> vec;
void dfs(int u, int Fa) {
    vis[u] = true, fa[u] = Fa, dep[u] = dep[Fa] + 1; vec.emplace_back(u);
    for(auto &v : G[u]) 
        if(!vis[v.first]) dfs(v.first, u);
}

inline void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> A[i];
    for(int i = 1; i <= n; i ++) lsh.emplace_back(i - A[i]), lsh.emplace_back(i + A[i] + INF);
    sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    for(int i = 1; i <= n; i ++) {
        int a = lower_bound(lsh.begin(), lsh.end(), i - A[i]) - lsh.begin() + 1;
        int b = lower_bound(lsh.begin(), lsh.end(), i + A[i] + INF) - lsh.begin() + 1;
        if(a == b) E[a].emplace_back(i);
        else G[a].push_back({b, i}), G[b].push_back({a, i});
    }

    bool flag = true;
    for(int i = 1; i <= lsh.size(); i ++) if(!vis[i]) {
        vec.clear(); dfs(i, 0); sort(vec.begin(), vec.end(), [](int a, int b) {return dep[a] > dep[b]; });
        for(auto &u : vec) {
            for(auto &v : G[u]) {
                if(v.first == fa[u]) continue;
                if(!used[v.second]) E[u].emplace_back(v.second);
            }
            if((int)E[u].size() % 2 == 1) {
                if(fa[u] == 0) {flag = false; break; }
                else E[u].emplace_back((lsh[u - 1] + lsh[fa[u] - 1] - INF) / 2), assert((lsh[u - 1] + lsh[fa[u] - 1] - INF) % 2 == 0);
            }
            for(int j = 0; j < E[u].size(); j += 2)
                assert((!used[E[u][j]]) && (!used[E[u][j + 1]])), used[E[u][j]] = used[E[u][j + 1]] = true, ans.push_back({E[u][j], E[u][j + 1]});
        }
        if(!flag) break;
    }

    if(flag) {
        cout << "Yes\n";
        for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
    } else cout << "No\n";

    for(int i = 1; i <= lsh.size(); i ++) vis[i] = false;
    for(int i = 1; i <= n; i ++) used[i] = false;
    for(int i = 1; i <= lsh.size(); i ++) E[i].clear(), G[i].clear();
    lsh.clear(), ans.clear();
}

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

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 99720kb

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: 286ms
memory: 115964kb

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
41079 41080
44703 44704
48193 48191
41950 41948
43984 43982
45654 45655
39778 39776
49803 49804
44377 44375
47508 47509
42711 42712
43509 43510
46336 46334
41578 41576
48726 48727
40402 40400
45264 45265
44946 44947
50550 50551
44448 44449
47922 47923
44152 44150
49528 49526
43756 43754
47178 47...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 16ms
memory: 97688kb

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: 237ms
memory: 124080kb

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: 552ms
memory: 112768kb

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
9775 16810
64517 64903
59285 67547
8534 68382
71199 13877
85146 89511
70149 29137
85560 81341
88879 97785
75540 87133
22008 85079
8303 44517
72263 89557
61627 82684
83843 84773
99556 49026
24525 83355
10990 79957
51117 77752
3313 8502
74867 24403
56526 83458
72637 94022
26324 37926
27644 42552
4...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 181ms
memory: 97808kb

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
648 650
683 685
687 689
690 692
736 738
746 748
539 540
542 543
546 547
548 549
554 555
557 559
564 565
576 577
578 580
608 609
615 617
624 625
884 885
890 892
907 909
908 910
921 922
881 882
929 930
944 945
756 757
778 779
792 793
804 805
824 826
839 840
846 847
859 860
142 14...

result:

ok 1000 Cases (1000 test cases)