QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222724#6550. Elimination Raceucup-team004#RE 0ms3516kbC++203.5kb2023-10-21 18:07:122023-10-21 18:07:13

Judging History

This is the latest submission verdict.

  • [2023-10-21 18:07:13]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 3516kb
  • [2023-10-21 18:07:12]
  • Submitted

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 500;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector a(n - 1, std::vector<int>(n));
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> a[i][j];
            a[i][j]--;
        }
    }

    for (int s = 0; s < n; s++) {
        std::vector<std::bitset<N>> adj(n - 1);
        for (int i = 0; i < n - 1; i++) {
            int k = std::find(a[i].begin(), a[i].end(), s) - a[i].begin();
            for (int j = k + 1; j < n; j++) {
                adj[i][a[i][j]] = 1;
            }
        }

        std::vector<int> yx(n, -1), xy(n - 1);
        std::vector<bool> vis(n - 1);
        std::bitset<N> visy{};

        auto find = [&](auto self, int x) -> bool {
            vis[x] = true;

            while (true) {
                auto a = adj[x] & ~visy;
                if (a.none()) {
                    break;
                }
                int y = a._Find_first();
                visy[y] = 1;
                if (yx[y] == -1 || (!vis[yx[y]] && self(self, yx[y]))) {
                    yx[y] = x;
                    xy[x] = y;
                    return true;
                }
            }
            return false;
        };
        bool ok = true;
        for (int i = 0; i < n - 1; i++) {
            if (!find(find, i)) {
                ok = false;
                break;
            }
            vis.assign(n - 1, false);
            visy = {};
        }

        if (ok) {
            std::cout << "Yes\n";
            std::vector<int> cur(n - 1, n - 1);
            std::vector<bool> del(n);
            for (int t = 0; t < n - 1; t++) {
                int u = -1;
                for (int i = 0; i < n - 1; i++) {
                    if (cur[i] == -1) {
                        continue;
                    }
                    while (del[cur[i]]) {
                        cur[i] -= 1;
                    }
                    if (xy[i] == a[i][cur[i]]) {
                        u = i;
                    }
                }
                if (u == -1) {
                    int x = -1;
                    std::vector<int> p(n, -1);
                    for (int i = 0; i < n - 1; i++) {
                        if (cur[i] == -1) {
                            continue;
                        }
                        x = xy[i];
                        p[xy[i]] = a[i][cur[i]];
                    }
                    for (int i = 0; i < n; i++) {
                        x = p[x];
                    }
                    std::vector<bool> cyc(n);
                    for (int i = 0; i < n; i++) {
                        cyc[x] = true;
                        x = p[x];
                    }
                    for (int i = 0; i < n - 1; i++) {
                        if (cur[i] == -1) {
                            continue;
                        }
                        if (cyc[xy[i]]) {
                            xy[i] = a[i][cur[i]];
                            u = i;
                        }
                    }
                }
                assert(u != -1);
                cur[u] = -1;
                del[xy[u]] = true;
                std::cout << u + 1 << " \n"[t == n - 2];
            }
        } else {
            std::cout << "No\n";
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
1 2 3 4
2 1 3 4
4 3 1 2

output:

Yes
3 2 1
No
No
No

result:

ok n=4, yes=1, no=3

Test #2:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

3
2 1 3
2 1 3

output:

No
Yes
1 2
No

result:

ok n=3, yes=1, no=2

Test #3:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

2
1 2

output:

Yes
1
No

result:

ok n=2, yes=1, no=1

Test #4:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

2
2 1

output:

No
Yes
1

result:

ok n=2, yes=1, no=1

Test #5:

score: -100
Runtime Error

input:

11
4 3 6 1 11 10 5 7 8 9 2
11 6 5 1 10 3 8 2 7 9 4
5 9 2 11 3 4 1 10 8 6 7
9 11 8 3 5 4 1 6 7 10 2
3 9 7 6 5 10 1 4 11 8 2
8 2 4 1 5 9 3 7 6 10 11
3 8 2 9 1 4 5 10 11 6 7
10 11 4 1 7 5 2 6 8 9 3
10 6 9 3 2 1 4 8 11 7 5
8 11 9 1 4 10 2 5 3 7 6

output:


result: