QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648210#5423. Perfect Matching0x3fffffffWA 277ms13756kbC++202.1kb2024-10-17 17:40:282024-10-17 17:40:33

Judging History

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

  • [2024-10-17 17:40:33]
  • 评测
  • 测评结果:WA
  • 用时:277ms
  • 内存:13756kb
  • [2024-10-17 17:40:28]
  • 提交

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>v;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v.push_back(i - a[i]);
        v.push_back(i + a[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int m = v.size() + 5;

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

    auto add = [&](int a, int b) {
        h[a].push_back(e.size());
        e.push_back({a, b});
    };

    for (int i = 1; i <= n; i++) {
        int x = lower_bound(v.begin(), v.end(), i - a[i]) - v.begin() + 1;
        int y = lower_bound(v.begin(), v.end(), i + a[i]) - v.begin() + 1;
        add(x, y);
        add(y, 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] = -1;
            if (ok != -1) {
                if (!vis[v] and i != (lst ^ 1)) {
                    ff(ff, v, 0);
                }
                if (hav[v] != -1) {
                    ans.push_back({hav[v], i / 2 + 1});
                    hav[v] = -1;
                } else if (hav[u] != -1) {
                    ans.push_back({hav[u], i / 2 + 1});
                    hav[u] = -1;
                } else {
                    hav[u] = i / 2 + 1;
                }
            }
        }
    };
    for (int i = 1; i <= v.size(); 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: -100
Wrong Answer
time: 277ms
memory: 13756kb

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
1 11
21 22
5 7
12 30
29 31
32 33
3 34
77 78
98 99
79 100
122 123
128 129
124 130
137 138
200 201
139 202
203 205
224 225
242 244
287 289
290 291
226 292
308 309
314 315
310 316
320 321
335 337
362 364
371 372
322 373
377 378
380 382
389 391
395 396
379 397
416 417
434 435
418 436
449 450
458 459...

result:

wrong answer abs(79-100) != abs(a[79]-a[100]) (test case 1)