QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771631#5423. Perfect Matchingchenlinxuan0226WA 459ms24920kbC++143.2kb2024-11-22 14:43:282024-11-22 14:43:35

Judging History

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

  • [2024-11-22 14:43:35]
  • 评测
  • 测评结果:WA
  • 用时:459ms
  • 内存:24920kb
  • [2024-11-22 14:43:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int T, n, a[100001], fa[100001], siz[100001], cnte, w[100001], v[100001], com[100001], q[100001],
    Left[100001];
map<int, vector<int>> s1, s2;
vector<int> Map[100001];

struct edge {
    int u, v, c;
} e[400001];

int find(int i) { return fa[i] = (i == fa[i]) ? i : find(fa[i]); }

void clear() {
    for (int i = 1; i <= n; i++) v[i] = 0, com[i] = 0;
}

void bfs(int s, int t) {
    int ta = 0;
    q[ta++] = s;
    v[s] = 1;
    int h = 0;
    while (h < ta) {
        int u = q[h++];
        for (int& e_ : Map[u]) {
            auto& [x, y, c] = e[e_];
            if (v[y])
                continue;
            v[y] = 1, com[y] = e_;
            if (y == t) {
                int now = y;
                while (now != s) e[com[now]].c ^= 1, e[com[now] ^ 1].c ^= 1, now = e[com[now]].u;
                return;
            }
            q[ta++] = y;
        }
    }
}

void merge(int x, int y) {
    ++cnte;
    e[cnte << 1] = { x, y, 0 };
    e[cnte << 1 | 1] = { y, x, 0 };
    Map[x].push_back(cnte << 1);
    Map[y].push_back(cnte << 1 | 1);
    if (find(x) == find(y))
        return;
    if ((siz[fa[x]] & 1) && (siz[fa[y]] & 1)) {
        int nowx = w[fa[x]], nowy = w[fa[y]];
        while (nowx && nowx != x)
            e[Left[nowx] << 1].c ^= 1, e[Left[nowx] << 1 | 1].c ^= 1, nowx = e[Left[nowx] << 1].u;
        while (nowy && nowy != y)
            e[Left[nowy] << 1].c ^= 1, e[Left[nowy] << 1 | 1].c ^= 1, nowy = e[Left[nowy] << 1].u;
        e[cnte << 1].c ^= 1;
        e[cnte << 1 | 1].c ^= 1;
        // clear(),bfs(w[fa[x]],w[fa[y]]);
        w[fa[y]] = w[fa[x]] = 0;
    }
    w[fa[y]] = w[fa[x]] | w[fa[y]];
    w[fa[x]] = 0;
    siz[fa[y]] += siz[fa[x]], siz[fa[x]] = 0, fa[fa[x]] = fa[y];
}
void onlymerge(int x, int y) {
    if (find(x) == find(y))
        return;
    siz[fa[y]] += siz[fa[x]], siz[fa[x]] = 0, fa[fa[x]] = fa[y];
}

int main() {
    // ios::sync_with_stdio(false),cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        cnte = 0;
        s1.clear();
        s2.clear();
        for (int i = 1; i <= n; i++)
            cin >> a[i], s1[a[i] - i].push_back(i), fa[i] = i, siz[i] = 1, Map[i].clear(), w[i] = i,
                                                    Left[i] = 0;
        for (int i = 1; i <= n; i++) s2[a[i] - (n - i + 1)].push_back(i);
        for (auto& [x, y] : s1)
            for (int i = 1; i < y.size(); i++) onlymerge(y[i - 1], y[i]);
        for (auto& [x, y] : s2)
            for (int i = 1; i < y.size(); i++) onlymerge(y[i - 1], y[i]);
        int o = 1;
        for (int i = 1; i <= n; i++) o &= !(siz[i] & 1);
        if (!o) {
            cout << "No\n";
            continue;
        }
        for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
        for (auto& [x, y] : s1)
            for (int i = 1; i < y.size(); i++) Left[y[i]] = cnte, merge(y[i - 1], y[i]);
        for (auto& [x, y] : s2)
            for (int i = 1; i < y.size(); i++) merge(y[i - 1], y[i]);
        cout << "Yes\n";
        for (int i = 1; i <= cnte; i++)
            if (e[i << 1].c)
                cout << e[i << 1].u << " " << e[i << 1].v << "\n";
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7840kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 459ms
memory: 24920kb

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
99986 99988
99974 99976
99968 99970
99965 99966
99962 99963
99959 99960
99957 99958
99954 99955
99947 99949
99945 99946
99933 99934
99917 99919
99912 99913
99902 99904
99878 99880
99875 99876
99854 99855
99836 99837
99833 99835
99825 99826
99819 99820
99800 99802
99767 99768
99744 99745
99737 99...

result:

wrong answer 797 appears more than once (test case 1)