제출 #1290108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290108		azamurai	Red-blue table (IZhO19_stones)	C++20	100 / 100	574 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], b[N][N];

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

int calc2() {
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int red = 0;
		for (int j = 1; j <= m; j++) {
			if (b[i][j] == '+') red++;
		}
		if (red > (m - red)) ans++;
	}
	for (int j = 1; j <= m; j++) {
		int blue = 0;
		for (int i = 1; i <= n; i++) {
			if (b[i][j] == '-') blue++;
		}
		if (blue > (n - blue)) ans++;
	}
	return ans;
}

void upd1(int limit) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][j] = '0';
		}
	}
	for (int i = 1; i <= n; i++) {
		cnt[i] = 0;
	}
	int need_x = (m + 2) / 2;
	int need_y = (n + 2) / 2;
	for (int j = 1; j <= limit; j++) {
		for (int i = 1; i <= n; i++) {
			used[i] = 0;
		}
		int amount = 0;
		vector <pair<int,int>> save;
		for (int i = 1; i <= n; i++) {
			save.push_back(mp(cnt[i], i));
		}
		sort(save.begin(), save.end());
		for (auto to : save) {
			int i = to.se;
			if (used[i] || amount == need_y) continue;
			if ((m - cnt[i]) < need_x) {
				used[i] = 1;
				cnt[i]++;
				a[i][j] = '-';
				amount++;
			}
		}
		for (auto to : save) {
			int i = to.se;
			if (used[i] || amount == need_y) continue;
			if ((m - cnt[i]) > need_x) {
				used[i] = 1;
				cnt[i]++;
				a[i][j] = '-';
				amount++;
			}
		}
		for (auto to : save) {
			int i = to.se;
			if (used[i] || amount == need_y) continue;
			if ((m - cnt[i]) == need_x) {
				used[i] = 1;
				cnt[i]++;
				a[i][j] = '-';
				amount++;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '0') a[i][j] = '+';
		}
	}
}

void upd2(int limit) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			b[i][j] = '0';
		}
	}
	for (int i = 1; i <= m; i++) {
		cnt[i] = 0;
	}
	int need_x = (m + 2) / 2;
	int need_y = (n + 2) / 2;
	for (int i = 1; i <= limit; i++) {
		for (int j = 1; j <= m; j++) {
			used[j] = 0;
		}
		int amount = 0;
		vector <pair<int,int>> save;
		for (int j = 1; j <= m; j++) {
			save.push_back(mp(cnt[j], j));
		}
		sort(save.begin(), save.end());
		for (auto to : save) {
			int j = to.se;
			if (amount == need_x || used[j]) continue;
			if ((n - cnt[j]) < need_y) {
				used[j] = 1;
				cnt[j]++;
				b[i][j] = '+';
				amount++;
			}
		}
		for (auto to : save) {
			int j = to.se;
			if (amount == need_x || used[j]) continue;
			if ((n - cnt[j]) > need_y) {
				used[j] = 1;
				cnt[j]++;
				b[i][j] = '+';
				amount++;
			}
		}
		for (auto to : save) {
			int j = to.se;
			if (amount == need_x || used[j]) continue;
			if ((n - cnt[j]) == need_y) {
				used[j] = 1;
				cnt[j]++;
				b[i][j] = '+';
				amount++;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (b[i][j] == '0') b[i][j] = '-';
		}
	}
}

void solve() {
	cin >> n >> m;
	int mxy = 0, svy;
	for (int i = m; i >= max(1, m - 10); i--) {
		upd1(i);
		if (calc1() > mxy) {
			mxy = calc1();
			svy = i;
		}
	}
	int mxx = 0, svx;
	for (int i = n; i >= max(1, n - 10); i--) {
		upd2(i);
		if (calc2() > mxx) {
			mxx = calc2();
			svx = i;
		}
	}
	upd1(svy);
	upd2(svx);
	if (calc1() > calc2()) {
		cout << calc1() << '\n';
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << a[i][j];
			}
			cout << '\n';
		}
	}
	else {
		cout << calc2() << '\n';
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << b[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: 31 / 31