Submission #503190

#	Time	Username	Problem	Language	Result	Execution time	Memory
503190		atoiz	Gardening (RMI21_gardening)	C++14	100 / 100	24 ms	860 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cassert>

using namespace std;

const int SMALL = 20;
bitset<SMALL * SMALL> small_prep[SMALL][SMALL];

void prep() {
	small_prep[2][2][1] = 1;
	for (int a = 2; a <= SMALL; a += 2) {
		for (int b = 2; b <= SMALL; b += 2) {
			if (a > b) { small_prep[a][b] = small_prep[b][a]; continue; }
			small_prep[a][b] |= small_prep[a - 2][b - 2] << 1;

			for (int c = 2; c < a; c += 2) {
				for (int x = 0; x < SMALL * SMALL; ++x) if (small_prep[c][b][x]) {
					small_prep[a][b] |= small_prep[a - c][b] << x;
				}
			}

			for (int c = 2; c < b; c += 2) {
				for (int x = 0; x < SMALL * SMALL; ++x) if (small_prep[a][c][x]) {
					small_prep[a][b] |= small_prep[a][b - c] << x;
				}
			}
		}
	}
}

bool check(int a, int b, int x) {
	if (a > b) return check(b, a, x);
	if (b < SMALL) return small_prep[a][b][x];
	if (a == 0) return x == 0;
	if (a == 2) return x == b / 2;
	if (x > (a / 2) * (b / 2)) return false;
	if (x == (a / 2) * (b / 2) - 1) return false;
	if (x < b / 2) return false;
	if (a == b && x == b / 2 + 1) return false;
	return true;
}

void solve(vector<vector<int>> &arr, int x0, int y0, int a, int b, int x, int &nxt) {
	assert(check(a, b, x));

	if (x == 1) {
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				arr[x0 + i][y0 + j] = nxt;
			}
		}
		++nxt;
		return;
	}

	if (check(a - 2, b - 2, x - 1)) {
		for (int i = 0; i < a; ++i) arr[x0 + i][y0] = arr[x0 + i][y0 + b - 1] = nxt;
		for (int j = 0; j < b; ++j) arr[x0][y0 + j] = arr[x0 + a - 1][y0 + j] = nxt;
		++nxt;
		solve(arr, x0 + 1, y0 + 1, a - 2, b - 2, x - 1, nxt);
		return;
	}

	static auto lb = [](int a, int b) { return max(a, b) / 2; };
	static auto ub = [](int a, int b) { return (a / 2) * (b / 2); };

	for (int c = 2; c < a; c += 2) {
		for (int y = max(lb(c, b), x - ub(a - c, b)); y <= min(ub(c, b), x - lb(a - c, b)); ++y) {
			if (check(c, b, y) && check(a - c, b, x - y)) {
				return solve(arr, x0, y0, c, b, y, nxt), solve(arr, x0 + c, y0, a - c, b, x - y, nxt);
			}
		}
	}

	for (int c = 2; c < b; c += 2) {
		for (int y = max(lb(a, c), x - ub(a, b - c)); y <= min(ub(a, c), x - lb(a, b - c)); ++y) {
			if (check(a, c, y) && check(a, b - c, x - y)) {
				return solve(arr, x0, y0, a, c, y, nxt), solve(arr, x0, y0 + c, a, b - c, x - y, nxt);
			}
		}
	}

	assert(false);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	prep();
	int t; cin >> t;
	while (t--) {
		int a, b, x; cin >> a >> b >> x;
		if (!check(a, b, x)) cout << "NO\n";
		else {
			vector<vector<int>> arr(a, vector<int>(b));
			int nxt = 1;
			solve(arr, 0, 0, a, b, x, nxt);
			cout << "YES\n";
			for (auto v : arr) {
				for (auto w : v) {
					cout << w << ' ';
				}
				cout << '\n';
			}
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22