QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471422 | #895. Color | Yansuan_HCl | RE | 1ms | 4420kb | C++20 | 2.7kb | 2024-07-10 21:04:40 | 2024-07-10 21:04:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define U(i,l,r) for (int i(l),END##i(r); i<=END##i; ++i)
#define D(i,l,r) for (int i(l),END##i(r); i>=END##i; --i)
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline))
#define vc vector
#define arr array
#define pb push_back
#define eb emplace_back
#define el '\n'
using ll = long long;
const int N = 405, M = N * N * 4;
struct eg { int v, f, pre; } e[M]; int tail[N], ptr;
void init() {
ms(tail, 0);
ptr = 1;
}
void ae(int u, int v, int f) {
e[++ptr] = {v, f, tail[u]};
tail[u] = ptr;
}
void add(int u, int v, int f) {
ae(u, v, f);
ae(v, u, 0);
}
int m, n;
int s, t;
int layer[N];
bool bfs() {
ms(layer, 0);
queue<int> q; q.push(s); layer[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int p = tail[u]; p; p = e[p].pre) if (e[p].f) {
int v = e[p].v;
if (!layer[v]) {
layer[v] = layer[u] + 1;
q.push(v);
}
}
}
return layer[t];
}
int dfs(int u, int in) {
if (!in) return 0;
if (u == t) return in;
int out = 0;
for (int &p = tail[u]; p; p = e[p].pre) {
auto &[v, f, _] = e[p];
if (f && layer[v] == layer[u] + 1) {
int c = dfs(v, min(in, f));
in -= c; f -= c;
out += c; e[p ^ 1].f += c;
if (!in) break;
}
}
return out;
}
int dinic() {
int ot[N]; memcpy(ot, tail, sizeof(ot));
int f = 0;
while (bfs()) {
int c = dfs(s, 1e9);
f += c;
memcpy(tail, ot, sizeof(ot));
}
return f;
}
int main() {
// freopen("arrebol.in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin >> n >> m;
if (!(m & 1)) {
cout << "No" << el;
return 0;
}
int to[N][N] {};
U (i, 1, n) U (j, 1, n - i) {
int c; cin >> c;
if (to[i][c] || to[i + j][c]) {
cout << "No" << el;
return 0;
}
to[i][c] = i + j;
to[i + j][c] = i;
}
{
int s1[N] {}, s2[N] {};
U (i, 1, n) U (c, 1, m)
if (to[i][c]) ++s2[c];
else ++s1[c];
U (c, 1, m) if (s2[c] / 2 + s1[c] > (m + 1) / 2) {
cout << "No" << el;
return 0;
}
}
for (; n <= m; ++n) {
init();
s = N - 1, t = N - 2;
U (i, 1, m) add(s, i, 1);
U (i, 1, n) add(m + i, t, 1);
vc<int> cons;
U (u, 1, n) U (i, 1, m) if (!to[u][i]) {
add(i, m + u, 1);
cons.pb(ptr);
}
int f = dinic();
assert(f == n);
int q = 0;
U (u, 1, n) U (i, 1, m) if (!to[u][i]) {
int p = cons[q++];
if (e[p].f) {
to[n + 1][i] = u;
to[u][i] = n + 1;
}
}
}
cout << "Yes" << el;
U (i, 1, m) {
int res[m + 2 - i] {};
U (c, 1, m) if (to[i][c] > i)
res[to[i][c] - i] = c;
U (j, 1, m + 1 - i)
cout << res[j] << ' ';
cout << el;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4420kb
input:
3 5 1 2 4
output:
Yes 1 2 4 3 5 4 3 5 2 5 1 3 2 1 4
result:
ok ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 4224kb
input:
4 5 1 2 3 3 2 1
output:
No
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
9 11 11 10 3 4 7 5 2 8 2 10 7 4 6 5 1 9 6 3 8 4 11 5 11 2 6 7 10 3 9 2 9 8 5 1 10 3
output:
No
result:
ok ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 4260kb
input:
12 11 2 11 8 9 1 3 10 7 5 4 6 5 11 10 6 4 9 8 7 1 3 3 8 4 9 7 2 10 6 1 5 2 6 1 4 9 10 7 11 2 6 3 1 7 4 7 8 10 3 9 5 5 1 8 11 10 11 4 3 2 6 5 9 2 11 8
output:
Yes 2 11 8 9 1 3 10 7 5 4 6 5 11 10 6 4 9 8 7 1 3 3 8 4 9 7 2 10 6 1 5 2 6 1 4 9 10 7 11 2 6 3 1 7 4 7 8 10 3 9 5 5 1 8 11 10 11 4 3 2 6 5 9 2 11 8
result:
ok ok
Test #5:
score: -100
Runtime Error
input:
3 9 2 8 4