QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471422#895. ColorYansuan_HClRE 1ms4420kbC++202.7kb2024-07-10 21:04:402024-07-10 21:04:40

Judging History

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

  • [2024-07-10 21:04:40]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4420kb
  • [2024-07-10 21:04:40]
  • 提交

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

output:


result: