QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186111#5423. Perfect Matching_LAP_WA 205ms8500kbC++141.9kb2023-09-23 07:45:192023-09-23 07:45:19

Judging History

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

  • [2023-09-23 07:45:19]
  • 评测
  • 测评结果:WA
  • 用时:205ms
  • 内存:8500kb
  • [2023-09-23 07:45:19]
  • 提交

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] && v != u) || (i ^ 1) == fa) continue;
        if(v != u) 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;
}

详细

Test #1:

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

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: 205ms
memory: 8500kb

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
99993 99962
99957 99954
99939 99927
99921 99896
99893 99890
99872 99870
99863 99849
99836 99830
99825 99819
99804 99795
99791 99788
99774 99771
99752 99750
99741 99723
99720 99716
99714 99710
99707 99699
99693 99686
99668 99659
99657 99642
99632 99630
99627 99617
99609 99596
99578 99572
99566 99...

result:

wrong answer abs(99993-99962) != abs(a[99993]-a[99962]) (test case 1)