oj.uz

Submission #972399

# Submission time Handle Problem Language Result Execution time Memory
972399 2024-04-30T11:41:58 Z colossal_pepe Red-blue table (IZhO19_stones) C++17
100 / 100
 633 ms 1768 KB 
#include <bits/stdc++.h>
using namespace std;

int t, n, m;

void rotate(vector<vector<bool>> &v) {
	int nv = v.size(), mv = v[0].size();
	vector<vector<bool>> vp(mv, vector<bool>(nv));
	for (int i = 0; i < nv; i++) {
		for (int j = 0; j < mv; j++) {
			vp[j][i] = !v[i][j];
		}
	}
	v = vp;
}

int solve(int nv, int mv, vector<vector<bool>> &v) {
	auto ok = [nv, mv, &v](int save) {
		vector<int> cnt(save, nv);
		priority_queue<pair<int, int>> pq;
		for (int i = 0; i < save; i++) {
			pq.push(make_pair(cnt[i], i));
		}
		int plus = (mv / 2) + 1 - (mv - save);
		for (int i = 0; i < nv; i++) {
			for (int j = 0; j < mv; j++) {
				v[i][j] = (j >= save);
			}
			for (int _ = 1; _ <= plus; _++) {
				auto [__, j] = pq.top();
				pq.pop();
				v[i][j] = 1;
				pq.push(make_pair(--cnt[j], j));
			}
		}
		bool ret = 1;
		for (int x : cnt) {
			ret &= (x > nv / 2);
		}
		return ret;
	};
	int lo = 0, hi = mv;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (ok(mid)) lo = mid;
		else hi = mid - 1;
	}
	if (ok(hi)) return nv + hi;
	ok(lo);
	return nv + lo;
}

int main() {
	cin >> t;
	while (t--) {
		cin >> n >> m;
		vector<vector<bool>> org(n, vector<bool>(m));
		int goodA = solve(n, m, org);
		vector<vector<bool>> alt(m, vector<bool>(n));
		int goodB = solve(m, n, alt);
		if (goodA < goodB) {
			swap(goodA, goodB);
			rotate(alt);
			swap(alt, org);
		}
		cout << goodA << '\n';
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << (org[i][j] ? '+' : '-');
			}
			cout << '\n';
		}
	}
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 7 ms 480 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 1460 KB Output is correct
2 Correct 510 ms 1504 KB Output is correct
3 Correct 486 ms 1356 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 1220 KB Output is correct
2 Correct 482 ms 1516 KB Output is correct
3 Correct 433 ms 1100 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 7 ms 480 KB Output is correct
5 Correct 313 ms 1460 KB Output is correct
6 Correct 510 ms 1504 KB Output is correct
7 Correct 486 ms 1356 KB Output is correct
8 Correct 353 ms 1220 KB Output is correct
9 Correct 482 ms 1516 KB Output is correct
10 Correct 433 ms 1100 KB Output is correct
11 Correct 38 ms 636 KB Output is correct
12 Correct 454 ms 1172 KB Output is correct
13 Correct 433 ms 1384 KB Output is correct
14 Correct 318 ms 1048 KB Output is correct
15 Correct 633 ms 1768 KB Output is correct
16 Correct 464 ms 1464 KB Output is correct
17 Correct 168 ms 820 KB Output is correct