Submission #526616

#	Time	Username	Problem	Language	Result	Execution time	Memory
526616		Zhora_004	Red-blue table (IZhO19_stones)	C++17	100 / 100	63 ms	1408 KiB

stones

#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 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31