QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186110#5423. Perfect Matching_LAP_WA 197ms8372kbC++141.9kb2023-09-23 07:43:272023-09-23 07:43:27

Judging History

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

  • [2023-09-23 07:43:27]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:8372kb
  • [2023-09-23 07:43:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = 2e5 + 10;
int n, A[N], h[N], e[M], ne[M], idx;
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
inline void add(int a, int b, bool flag) {add(a, b), add(b, a); }
vector<int> lsh;

vector<pair<int, int>> ans;
bool vis[N], used[M];
bool dfs(int u, int fa) { vis[u] = true;
    vector<int> E;
    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i]; if(vis[v] || (i ^ 1) == fa) continue;
        dfs(v, i); if(!used[i]) used[i] = used[i ^ 1] = true, E.emplace_back(i / 2 + 1);
    }

    if((int)E.size() % 2 == 1 && fa == -1) return false;
    if((int)E.size() % 2 == 1) used[fa] = used[fa ^ 1] = true, E.emplace_back(fa / 2 + 1);
    for(int i = 0; i < E.size(); i += 2) ans.push_back({E[i], E[i + 1]});
    return true;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    memset(h, -1, sizeof h);

    int T; cin >> T;
    while(T --) {
        cin >> n; memset(h + 1, -1, sizeof(int) * (2 * n)), idx = 0;
        lsh.clear(), ans.clear();
        memset(used + 1, false, sizeof(bool) * (2 * n)), memset(vis + 1, false, sizeof(bool) * (2 * 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]);
        sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());

        for(int i = 1; i <= n; i ++) 
            add(lower_bound(lsh.begin(), lsh.end(), i - A[i]) - lsh.begin() + 1, lower_bound(lsh.begin(), lsh.end(), i + A[i]) - lsh.begin() + 1, true);

        bool flag = true;
        for(int i = 1; i <= lsh.size(); i ++) 
            if(!vis[i]) flag = flag && dfs(i, -1);
        if(flag) {
            cout << "Yes\n";
            for(auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
        } else cout << "No\n";
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 197ms
memory: 8372kb

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:

No
No
Yes
99963 99947
99939 99932
99924 99914
99908 99900
99881 99879
99873 99869
99857 99852
99839 99827
99813 99795
99792 99788
99779 99773
99770 99765
99746 99744
99738 99714
99705 99701
99690 99677
99674 99672
99663 99657
99647 99639
99636 99630
99627 99624
99618 99615
99597 99593
99588 99581
99...

result:

wrong answer std outputs a valid answer while participant doesn't (test case 1)