Submission #871687

#	Time	Username	Problem	Language	Result	Execution time	Memory
871687		TAhmed33	Gardening (RMI21_gardening)	C++98	11 / 100	15 ms	856 KiB

Main

#include <bits/stdc++.h>
using namespace std;
/*
const int n = 20;
bool dp[n + 1][n + 1][n * n + 1];
int main () {
	for (int i = 2; i <= n; i += 2) {
		for (int j = 2; j <= n; j += 2) {
			for (int k = 1; k <= i * j; k++) {
				if (i == 2 && j == 2 && k == 1) {
					dp[i][j][k] = 1;
					continue;
				}
				dp[i][j][k] = dp[i - 2][j - 2][k - 1];
				for (int l = 1; l < k; l++) {
					for (int s = 2; s < i; s += 2) {
						dp[i][j][k] |= dp[s][j][l] & dp[i - s][j][k - l];
					}
					for (int s = 2; s < j; s += 2) {
						dp[i][j][k] |= dp[i][s][l] & dp[i][j - s][k - l];
					}
				}
			}
		}
	}
	for (int i = 2; i <= n; i += 2) {
		for (int j = 2; j <= n; j += 2) {
			for (int l = 1; l <= i * j; l++) {
				if (dp[i][j][l]) {
					cout << "YES: " << i << " " << j << " " << l << '\n';
				} else {
					cout << "NO: " << i << " " << j << " " << l << '\n';
				}
			}
		}
	}
		n and m are even
		max(n / 2, m / 2) <= k <= n * m / 4, k != n * m / 4 - 1
		if n == m then k != n / 2 - 1
	pattern observation level el wa7sh
}*/
vector <vector <int>> arr;
int cnt = 0;
bool valid (int n, int m, int k) {
	if (n <= 0 || m <= 0 || k <= 0) return 0;
	if (n & 1) return 0;
	if (m & 1) return 0;
	if (max(n / 2, m / 2) > k || k > n * m / 4 || k == n * m / 4 - 1 || (n == m && k == n / 2 - 1)) return 0;
	return 1;
}
void recurse (int x1, int y1, int x2, int y2, int k) {
	if (k == 0 || x1 > x2 || y1 > y2) return;
	int n = x2 - x1 + 1, m = y2 - y1 + 1;
	assert(valid(n, m, k));
	if (k < n * m / 4 - (n + m) || valid(n - 2, m - 2, k - 1)) {
		cnt++;
		for (int i = x1; i <= x2; i++) arr[i][y1] = arr[i][y2] = cnt;
		for (int i = y1; i <= y2; i++) arr[x1][i] = arr[x2][i] = cnt;
		recurse(x1 + 1, y1 + 1, x2 - 1, y2 - 1, k - 1);
		return;
	}
	if (k == n * m / 4) {
		for (int i = x1; i < x2; i += 2) {
			for (int j = y1; j < y2; j += 2) {
				cnt++;
				arr[i][j] = arr[i][j + 1] = arr[i + 1][j] = arr[i + 1][j + 1] = cnt;
			}
		}
		return;
	}
	for (int l = 2; l < n; l += 2) {
		if (valid(l, m, (l * m / 4)) && valid(n - l, m, k - (l * m) / 4)) {
			recurse(x1, y1, x1 + l - 1, y2, (l * m) / 4);
			recurse(x1 + l, y1, x2, y2, k - l * m / 4);
			return;
		}
	}
	for (int l = 2; l < m; l += 2) {
		if (valid(n, l, (l * n / 4)) && valid(n, m - l, k - (l * n) / 4)) {
			recurse(x1, y1, x2, y1 + l - 1, (l * n) / 4);
			recurse(x1, y1 + l, x2, y2, k - l * n / 4);
			return;
		}
	}
}
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, m, k;
		cin >> n >> m >> k;
		if (!valid(n, m, k)) {
			cout << "NO\n"; continue;
		}
		cout << "YES\n";
		arr.clear(); arr = vector <vector <int>> (n + 1, vector <int> (m + 1)); cnt = 0;
		recurse(1, 1, n, m, k);
		assert(k == cnt);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << arr[i][j] << " ";
			}
			cout << '\n';
		}
		cout << '\n';
	}
}

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