제출 #1288607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288607		azamurai	Red-blue table (IZhO19_stones)	C++20	69 / 100	17 ms	4428 KiB

stones

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define Sz(x) (int)x.size()

const int N = 1005;
int n, m, cnt[N], used[N];
char a[N][N];

int calc() {
	int res = 0;
	for (int i = 1; i <= n; i++) {
		int blue = 0, red = 0;
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '-') blue++;
			else red++;
		}
		if (red > blue) res++;
	}
	for (int j = 1; j <= m; j++) {
		int blue = 0, red = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i][j] == '-') blue++;
			else red++;
		}
		if (blue > red) res++;
	}
	return res;
}

void solve() {
	cin >> n >> m;
	if (min(n, m) == 1) {
		if (n == 1) {
			for (int j = 1; j <= m; j++) {
				a[1][j] = '-';
			}
		}
		else {
			for (int i = 1; i <= n; i++) {
				a[i][1] = '+';
			}
		}
	}
	else if (min(n, m) == 2) {
		if (n == 2) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= m; j++) {
					a[i][j] = '-';
				}
			}
		}
		else {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= m; j++) {
					a[i][j] = '+';
				}
			}
		}
	}
	else if (min(n,m) == 3) {
		if (n == 3) {
			for (int i = 1; i <= 2; i++) {
				for (int j = 1; j <= m; j++) {
					a[i][j] = '-';
				}
			}
			for (int j = 1; j <= m; j++) {
				a[3][j] = '+';
			}
		}
		else {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= 2; j++) {
					a[i][j] = '+';
				}
			}
			for (int i = 1; i <= n; i++) {
				a[i][3] = '-';
			}
		}
	}
	else if (min(n, m) == 4) {
		if (n == 4) {
			for (int i = 1; i <= 3; i++) {
				for (int j = 1; j <= m; j++) {
					a[i][j] = '-';
				}
			}
			for (int j = 1; j <= m; j++) {
				a[4][j] = '+';
			}
		}
		else {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= 3; j++) {
					a[i][j] = '+';
				}
			}
			for (int i = 1; i <= n; i++) {
				a[i][4] = '-';
			}
		}
	}
	else if (min(n, m) == 5) {
		if (n == 5) {
			for (int j = 1; j <= m; j++) {
				if (j % 3 == 1) {
					a[1][j] = a[2][j] = '+';
					a[3][j] = a[4][j] = a[5][j] = '-';
				}
				else if (j % 3 == 2) {
					a[1][j] = a[3][j] = '+';
					a[2][j] = a[4][j] = a[5][j] = '-';
				}
				else {
					a[2][j] = a[3][j] = '+';
					a[1][j] = a[4][j] = a[5][j] = '-';
				}
			}
		}
		else {
			for (int i = 1; i <= n; i++) {
				if (i % 3 == 1) {
					a[i][1] = a[i][2] = '-';
					a[i][3] = a[i][4] = a[i][5] = '+';
				}
				else if (i % 3 == 2) {
					a[i][1] = a[i][3] = '-';
					a[i][2] = a[i][4] = a[i][5] = '+';
				}
				else {
					a[i][2] = a[i][3] = '-';
					a[i][1] = a[i][4] = a[i][5] = '+';
				}
			}
		}
	}
	else if (n % 2 == 1 && m % 2 == 1) {
		if (n < m) {
			for (int j = 1; j < m; j++) {
				if (j % 2 == 1) {
					for (int i = 1; i <= n / 2; i++) {
						a[i][j] = '+';
					}
					for (int i = n / 2 + 1; i <= n; i++) {
						a[i][j] = '-';
					}
				}
				else {
					for (int i = 1; i <= n / 2 + 1; i++) {
						a[i][j] = '-';
					}
					for (int i = n / 2 + 2; i <= n; i++) {
						a[i][j] = '+';
					}
				}
			}
			for (int i = 1; i <= n; i++) {
				a[i][m] = '+';
			}
		}
		else {
			for (int i = 1; i < n; i++) {
				if (i % 2 == 1) {
					for (int j = 1; j <= m / 2; j++) {
						a[i][j] = '-';
					}
					for (int j = m / 2 + 1; j <= m; j++) {
						a[i][j] = '+';
					}
				}
				else {
					for (int j = 1; j <= m / 2 + 1; j++) {
						a[i][j] = '+';
					}
					for (int j = m / 2 + 2; j <= m; j++) {
						a[i][j] = '-';
					}
				}
			}
			for (int j = 1; j <= m; j++) {
				a[n][j] = '-';
			}
		}
	}
	else {
		int Cntx, Cnty;
		for (int cntx = 0, mx = 0; cntx <= n; cntx++) {
			for (int cnty = 0; cnty <= m; cnty++) {
				int red = cntx * ((m + 2) / 2);
				int blue = cnty * ((n + 2) / 2);
				if (red + blue <= n * m && cntx + cnty > mx) {
					Cntx = cntx;
					Cnty = cnty;
					mx = cntx + cnty;
				}
			}
		}
		for (int i = 1; i <= n; i++ ) {
			for (int j = 1; j <= m; j++) {
				a[i][j] = '0';
				cnt[j] = 0;
				used[j] = 0;
			}
		}
		int need_y = (n + 2) / 2;
		int need_x = (m + 2) / 2;
		for (int i = 1; i <= Cntx; i++) {
			int amount = 0;
			for (int j = 1; j <= m; j++) {
				used[j] = 0;
			}
			for (int j = 1; j <= m; j++) {
				if (amount == need_x) break;
				if ((n - cnt[j]) < need_y) {
					amount++;
					cnt[j]++;
					used[j] = 1;
					a[i][j] = '+';
				}
			}
			if (amount == need_x) continue;
			vector <pair<int,int>> save;
			for (int j = 1; j <= m; j++) {
				if (used[j] || (n - cnt[j]) <= need_y) continue;
				save.push_back(mp(cnt[j], j));
			}
			sort(save.begin(), save.end());
			for (auto to : save) {
				if (amount == need_x) break;
				amount++;
				cnt[to.se]++;
				used[to.se] = 1;
				a[i][to.se] = '+';
			}
			if (amount == need_x) continue;
			for (int j = 1; j <= m; j++) {
				if (used[j] || (n - cnt[j]) != need_y || amount == need_x) continue;
				amount++;
				cnt[j]++;
				used[j] = 1;
				a[i][j] = '+';
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == '0') a[i][j] = '-';
			}
		}
	}
	cout << calc() << '\n';
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << a[i][j];
		}
		cout << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	
	for (int T = 1; T <= t; T++) {
		solve();
		//cout << '\n';
	}
}

• Subtask 1: 17 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 0 / 31