This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << arr[i][j] << " ";
}
cout << '\n';
}
cout << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |