QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263685#5423. Perfect MatchingKhNURE_KIVIAC ✓466ms24888kbC++233.6kb2023-11-25 02:58:442023-11-25 02:58:44

Judging History

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

  • [2023-11-25 02:58:44]
  • 评测
  • 测评结果:AC
  • 用时:466ms
  • 内存:24888kb
  • [2023-11-25 02:58:44]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

const int max_n = 1e5 + 42, inf = 1000111222;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<pair<int, int> > g[max_n * 2];

int h[max_n * 2];

bool used[max_n];

vector<pair<int, int> > ans;

void dfs(int v, int par, int par_edg) {
    for(auto& to : g[v])
        if(h[to.fi] == -1) {
            h[to.fi] = h[v] + 1;
            dfs(to.fi, to.fi, to.se);
        }
    vector<int> edges;
    for(auto& to : g[v])
        if(!used[to.se] && h[to.fi] > h[v])
            edges.pb(to.se);
    if(len(edges) % 2 && par_edg != -1) edges.pb(par_edg);
    for(int i = 1; i < len(edges); i += 2) {
        used[edges[i]] = used[edges[i - 1]] = true;
        ans.pb({edges[i], edges[i - 1]});
    }
}

void solve() {
    ans.clear();
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> bs, cs;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        bs.pb(a[i] - i);
        cs.pb(a[i] + i);
    }
    sort(all(bs));
    sort(all(cs));
    bs.resize(unique(all(bs)) - bs.begin());
    cs.resize(unique(all(cs)) - cs.begin());
    for(int i = 0; i < n; i++) {
        int b_ind = lower_bound(all(bs), a[i] - i) - bs.begin();
        int c_ind = lower_bound(all(cs), a[i] + i) - cs.begin();
        g[b_ind].pb({len(bs) + c_ind, i});
        g[len(bs) + c_ind].pb({b_ind, i});
    }
    for(int v = 0; v < len(bs) + len(cs); v++) {
        if(h[v] != -1) continue;
        dfs(v, -1, -1);
    }
    if(len(ans) != n / 2) cout << "No\n";
    else {
        cout << "Yes\n";
        for(auto& x : ans) cout << x.fi + 1 << ' ' << x.se + 1 << '\n';
    }
    for(int i = 0; i < n; i++) used[i] = false;
    for(int i = 0; i < len(bs) + len(cs); i++) { g[i].clear(); h[i] = -1; }
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i = 0; i < max_n * 2; i++) h[i] = -1;

    int t = 1;

    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 247ms
memory: 22904kb

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
139 79
244 202
310 289
322 316
382 337
451 397
463 460
517 481
526 520
568 556
661 619
763 736
853 790
934 904
988 979
1105 1090
1219 1162
1285 1273
1405 1294
1456 1411
1531 1459
1561 1555
1615 1588
1630 1618
1669 1651
1723 1684
1915 1738
2026 1972
2092 2029
2197 2155
2305 2290
2353 2350
2431 24...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 9092kb

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

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 223ms
memory: 24888kb

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

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 466ms
memory: 19648kb

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
26518 8564
1121 63463
129 36817
95315 8931
28 89504
81303 70110
16772 13611
778 34736
80993 88310
74032 11544
80608 33052
1661 3199
3633 47380
19162 3408
87006 59542
416 97729
73052 62860
56229 35450
9450 55641
2005 99552
4926 84101
92548 81132
83637 41302
28333 92168
3610 71221
37367 78597
8494...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 151ms
memory: 9216kb

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
5 3
28 26
38 29
43 41
49 45
68 57
71 70
83 74
112 87
119 118
124 122
129 126
139 134
142 141
146 143
165 151
175 170
178 177
184 183
203 200
208 205
219 212
226 220
257 243
268 266
273 270
277 274
285 284
300 298
313 312
324 323
328 326
335 332
345 339
359 354
365 361
370 366
3...

result:

ok 1000 Cases (1000 test cases)