Submission #645099

#TimeUsernameProblemLanguageResultExecution timeMemory
645099VanillaGardening (RMI21_gardening)C++17
5 / 100
27 ms724 KiB
#include <bits/stdc++.h> typedef long long int64; using namespace std; int n,m,k; bool build (int i1, int j1, int i2, int j2, vector <vector <int> >& a, int k) { int can = (i2 - i1 + 1) * (j2 - j1 + 1) / 4; // cout << i1 << " " << j1 << " " << i2 << " " << j2 << " " << k << " " << can << "\n"; if (!can) return (!k); if (can > k) { for (int j = j1; j <= j2; j++){ a[i1][j] = a[i2][j] = k; } for (int i = i1; i <= i2; i++){ a[i][j1] = a[i][j2] = k; } return build(i1 + 1, j1 + 1, i2 - 1, j2 - 1, a, k - 1); } else if (can == k){ for (int i = i1; i < i2; i+=2){ for (int j = j1; j < j2; j+=2){ a[i][j] = a[i][j+1] = a[i+1][j] = a[i+1][j+1] = k--; } } return 1; } return 0; } bool build2 (int i1, int j1, int i2, int j2, vector <vector <int> >& a, int k) { int can = (i2 - i1 + 1) * (j2 - j1 + 1) / 4; // cout << i1 << " " << j1 << " " << i2 << " " << j2 << " " << k << " " << can << "\n"; if (!can) return (!k); if (can > k) { for (int j = j1; j <= j2; j++){ a[i1][j] = a[i2][j] = k; } for (int i = i1; i <= i2; i++){ a[i][j1] = a[i][j2] = k; } return build2(i1 + 1, j1 + 1, i2 - 1, j2 - 1, a, k - 1); } else if (can == k){ for (int i = i1; i < i2; i+=2){ for (int j = j1; j < j2; j+=2){ a[i][j] = a[i][j+1] = a[i+1][j] = a[i+1][j+1] = k--; } } return 1; } return 0; } void t1 (int i1, int j1, int i2, int j2, vector <vector <int> >& a, int k) { for (int i = i1; i < i2; i+=2){ for (int j = j1; j < j2; j+=2){ a[i][j] = a[i][j+1] = a[i+1][j] = a[i+1][j+1] = k--; } } } void t2 (int i1, int j1, int i2, int j2, vector <vector <int> >& a, int k) { if (i1 >= i2) return; for (int j = j1; j <= j2; j++){ a[i1][j] = a[i2][j] = k; } for (int i = i1; i <= i2; i++){ a[i][j1] = a[i][j2] = k; } t2(i1 + 1, j1 + 1, i2 - 1, j2 - 1, a, k - 1); } void solve() { cin >> n >> m >> k; if (n % 2 || m % 2) { cout << "NO\n"; return; } vector <vector <int> > a (n, vector <int> (m)); if (n == 2) { if (n * m / 4 == k) { t1(0, 0, n - 1, m - 1, a, k); } else { cout << "NO\n"; return; } } else if (n == 4) { // n <= 4 int pot = n * m / 4; int f = -2; if (pot == k) f = -1; for (int i = 3; i < m; i+=3){ if (pot - 2 == k) { f = i; break; } pot-=2; } // clog << f << "\n"; if (f == -2) { cout << "NO\n"; return; } for (int p = 0; p < f; p+=4){ t2(0, p, n - 1, p + 3, a, k); k-=2; } t1(0, f + 1, n - 1, m - 1, a, k); } cout << "YES\n"; for (auto i: a) { for (auto j: i) { cout << j << " "; } cout << "\n"; } // if (n == m) { // vector <vector <int> > a (n, vector <int> (m)); // if (build (0, 0, n - 1, n - 1, a, k)) { // cout << "YES\n"; // for (auto i: a) { // for (auto j: i) { // cout << j << " "; // } // cout << "\n"; // } // } // else { // cout << "NO\n"; // } // } // else { // vector <vector <int> > a (n, vector <int> (m)); // if (build2 (0, 0, n - 1, m - 1, a, k)) { // cout << "YES\n"; // for (auto i: a) { // for (auto j: i) { // cout << j << " "; // } // cout << "\n"; // } // } // else { // cout << "NO\n"; // } // } } int main() { cin.tie(0); ios::sync_with_stdio(0); int t; cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...