QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648233#5423. Perfect Matching0x3fffffffWA 293ms13640kbC++202.0kb2024-10-17 17:47:582024-10-17 17:48:02

Judging History

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

  • [2024-10-17 17:48:02]
  • 评测
  • 测评结果:WA
  • 用时:293ms
  • 内存:13640kb
  • [2024-10-17 17:47:58]
  • 提交

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), pp(m * 4 + 10,1);

    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] = 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 <= 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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3572kb

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: 293ms
memory: 13640kb

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)