QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648300#5423. Perfect Matching0x3fffffffRE 1ms3592kbC++202.3kb2024-10-17 18:11:152024-10-17 18:11:15

Judging History

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

  • [2024-10-17 18:11:15]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3592kb
  • [2024-10-17 18:11:15]
  • 提交

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 + 1);
    vector<array<int, 2>>e;
    vector<int>vis(m + 1), hav(m + 1), pp(m * 2 + 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: 1ms
memory: 3592kb

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
Runtime Error

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:


result: