oj.uz

Submission #526616

# Submission time Handle Problem Language Result Execution time Memory
526616 2022-02-15T16:54:24 Z Zhora_004 Red-blue table (IZhO19_stones) C++17
100 / 100
 63 ms 1408 KB 
#include <iostream>
#include <vector>
#include <queue>
#define sz(a) ((int)((a).size()))
using namespace std;


vector<vector<bool>> rotate(vector<vector<bool>>& v)
{
	int n = sz(v), m = sz(v[0]);
	vector<vector<bool>> res(m, vector<bool>(n));
	for (int j = m - 1; j >= 0; j--) for (int i = 0; i < n; i++) res[m - j - 1][i] = v[i][j];
	return res;
}

void test_case()
{
	int n, m;
	cin >> n >> m;
	bool rotated = 0;
	if (n > m)
	{
		rotated = 1;
		swap(n, m);
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for (int i = 0; i < m; i++) pq.push({ 0, i });
	int till = (n + 1) / 2;
	int cnt = m / 2 + 1;
	vector<vector<bool>> bd(n, vector<bool>(m));
	for (int i = 0; i < n; i++)
	{
		vector<pair<int, int>> vec;
		bool can = 1;
		while (sz(vec) != cnt)
		{
			int a = pq.top().first, b = pq.top().second;
			pq.pop();
			if (a + 1 == till)
			{
				can = 0;
				break;
			}
			vec.push_back({ a + 1, b });
		}
		if (!can) break;
		for (pair<int, int>& p : vec)
		{
			bd[i][p.second] = 1;
			pq.push({ p.first, p.second });
		}
	}
	if (rotated)
	{
		bd = rotate(bd);
		swap(n, m);
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) bd[i][j] = !bd[i][j];
	}
	int c = 0;
	for (int i = 0; i < n; i++)
	{
		int a = 0, b = 0;
		for (int j = 0; j < m; j++)
		{
			if (bd[i][j]) a++;
			else b++;
		}
		if (a > b) c++;
	}
	for (int j = 0; j < m; j++)
	{
		int a = 0, b = 0;
		for (int i = 0; i < n; i++)
		{
			if (bd[i][j]) a++;
			else b++;
		}
		if (b > a) c++;
	}
	cout << c << "\n";
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (bd[i][j]) cout << '+';
			else cout << '-';
		}
		cout << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc;
	cin >> tc;
	while (tc--)
		test_case();

	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1364 KB Output is correct
2 Correct 60 ms 1292 KB Output is correct
3 Correct 58 ms 1340 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1220 KB Output is correct
2 Correct 53 ms 1236 KB Output is correct
3 Correct 45 ms 1124 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 63 ms 1364 KB Output is correct
6 Correct 60 ms 1292 KB Output is correct
7 Correct 58 ms 1340 KB Output is correct
8 Correct 52 ms 1220 KB Output is correct
9 Correct 53 ms 1236 KB Output is correct
10 Correct 45 ms 1124 KB Output is correct
11 Correct 16 ms 588 KB Output is correct
12 Correct 50 ms 1160 KB Output is correct
13 Correct 57 ms 1220 KB Output is correct
14 Correct 40 ms 980 KB Output is correct
15 Correct 58 ms 1408 KB Output is correct
16 Correct 50 ms 1092 KB Output is correct
17 Correct 25 ms 764 KB Output is correct