QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222724 | #6550. Elimination Race | ucup-team004# | RE | 0ms | 3516kb | C++20 | 3.5kb | 2023-10-21 18:07:12 | 2023-10-21 18:07:13 |
Judging History
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