oj.uz

Submission #520379

# Submission time Handle Problem Language Result Execution time Memory
520379 2022-01-29T18:11:17 Z Alex_tz307 Gardening (RMI21_gardening) C++17
100 / 100
 24 ms 1088 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1 << 8;
const int64_t P = 1LL << 40;
const int p = 1 << 20;
bitset<kN> ok[kN][kN];
unordered_set<int64_t> states;
vector<vector<int>> sol;

inline bool checkData(const int &n, const int &m, const int &k) {
  if (n == 0 || m == 0 || k == 0 || n % 2 || m % 2 || k < max(n, m) / 2 || k > n * m / 4 ||
      k == n * m / 4 - 1 || (n == m && k == n / 2 + 1)) {
    return false;
  }
  return true;
}

inline int64_t convert(const int &n, const int &m, const int &k) {
  return P * k + (int64_t)p * n + m;
}

inline bool checkState(const int &n, const int &m, const int &k) {
  if (!checkData(n, m, k)) {
    return false;
  }
  if (k == n * m / 4) {
    return true;
  }
  if (max({n, m, k}) < kN) {
    return ok[n][m][k];
  }
  return states.count(convert(n, m, k));
}

inline void addState(const int &n, const int &m, const int &k) {
  if (max({n, m, k}) < kN) {
    ok[n][m][k] = true;
  } else {
    states.emplace(convert(n, m, k));
  }
}

bool check(const int &n, const int &m, const int &k) {
  if (checkState(n, m, k)) {
    return true;
  }
  if (!checkData(n, m, k)) {
    return false;
  }
  if (check(n - 2, m - 2, k - 1)) {
    addState(n, m, k);
    return true;
  }
  for (int i = 2; i < n; i += 2) {
    for (int k1 = max(i, m) / 2; k1 <= i * m / 4 && k1 < k; ++k1) {
      if (check(i, m, k1) && check(n - i, m, k - k1)) {
        addState(n, m, k);
        return true;
      }
      if (k - k1 < max(n - i, m) / 2) {
        break;
      }
    }
  }
  for (int j = 2; j < m; j += 2) {
    for (int k1 = max(n, j) / 2; k1 <= n * j / 4 && k1 < k; ++k1) {
      if (check(n, j, k1) && check(n, m - j, k - k1)) {
        addState(n, m, k);
        return true;
      }
      if (k - k1 < max(n, m - j) / 2) {
        break;
      }
    }
  }
  return false;
}

inline void addBorder(const int &x1, const int &y1, const int &x2, const int &y2, const int &k) {
  for (int i = x1; i <= x2; ++i) {
    sol[i][y1] = sol[i][y2] = k;
  }
  for (int j = y1; j <= y2; ++j) {
    sol[x1][j] = sol[x2][j] = k;
  }
}

inline void inc(const int &x1, const int &y1, const int &x2, const int &y2, const int &k) {
  for (int i = x1; i <= x2; ++i) {
    for (int j = y1; j <= y2; ++j) {
      sol[i][j] += k;
    }
  }
}

void build(const int &n, const int &m, const int &k, const int &x1, const int &y1, const int &x2, const int &y2) {
  if (n == 2 && m == 2 && k == 1) {
    sol[x1][y1] = sol[x1][y2] = sol[x2][y1] = sol[x2][y2] = 1;
    return;
  }
  if (checkState(n - 2, m - 2, k - 1)) {
    addBorder(x1, y1, x2, y2, k);
    build(n - 2, m - 2, k - 1, x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    return;
  }
  for (int i = 2; i < n; i += 2) {
    for (int k1 = max(i, m) / 2; k1 <= i * m / 4 && k1 < k; ++k1) {
      if (checkState(i, m, k1) && checkState(n - i, m, k - k1)) {
        build(i, m, k1, x1, y1, x1 + i - 1, y2);
        build(n - i, m, k - k1, x1 + i, y1, x2, y2);
        inc(x1 + i, y1, x2, y2, k1);
        return;
      }
      if (k - k1 < max(n - i, m) / 2) {
        break;
      }
    }
  }
  for (int j = 2; j < m; j += 2) {
    for (int k1 = max(n, j) / 2; k1 <= n * j / 4 && k1 < k; ++k1) {
      if (checkState(n, j, k1) && checkState(n, m - j, k - k1)) {
        build(n, j, k1, x1, y1, x2, y1 + j - 1);
        build(n, m - j, k - k1, x1, y1 + j, x2, y2);
        inc(x1, y1 + j, x2, y2, k1);
        return;
      }
      if (k - k1 < max(n, m - j) / 2) {
        break;
      }
    }
  }
}

void testCase() {
  int n, m, k;
  cin >> n >> m >> k;
  if (!check(n, m, k)) {
    cout << "NO\n";
    return;
  }
  cout << "YES\n";
  sol = vector<vector<int>>(n + 1, vector<int>(m + 1));
  build(n, m, k, 1, 1, n, m);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cout << sol[i][j] << ' ';
    }
    cout << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> tests;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 852 KB Correct! Azusa and Laika like the garden :)

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 852 KB Correct! Azusa and Laika like the garden :)
2 Correct 11 ms 592 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 588 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 852 KB Correct! Azusa and Laika like the garden :)
2 Correct 11 ms 592 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 588 KB Correct! Azusa and Laika like the garden :)
4 Correct 11 ms 576 KB Correct! Azusa and Laika like the garden :)
5 Correct 11 ms 616 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 828 KB Correct! Azusa and Laika like the garden :)
2 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
3 Correct 8 ms 716 KB Correct! Azusa and Laika like the garden :)
4 Correct 11 ms 844 KB Correct! Azusa and Laika like the garden :)
5 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
6 Correct 14 ms 820 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 844 KB Correct! Azusa and Laika like the garden :)
8 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
9 Correct 9 ms 736 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
11 Correct 10 ms 828 KB Correct! Azusa and Laika like the garden :)
12 Correct 9 ms 756 KB Correct! Azusa and Laika like the garden :)
13 Correct 8 ms 688 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 452 KB Correct! Azusa and Laika like the garden :)
2 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
3 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
4 Correct 5 ms 588 KB Correct! Azusa and Laika like the garden :)
5 Correct 6 ms 668 KB Correct! Azusa and Laika like the garden :)
6 Correct 3 ms 576 KB Correct! Azusa and Laika like the garden :)
7 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
8 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
9 Correct 5 ms 588 KB Correct! Azusa and Laika like the garden :)
10 Correct 4 ms 612 KB Correct! Azusa and Laika like the garden :)
11 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
12 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
13 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
14 Correct 4 ms 580 KB Correct! Azusa and Laika like the garden :)
15 Correct 3 ms 572 KB Correct! Azusa and Laika like the garden :)
16 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
17 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 852 KB Correct! Azusa and Laika like the garden :)
2 Correct 11 ms 592 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 588 KB Correct! Azusa and Laika like the garden :)
4 Correct 11 ms 576 KB Correct! Azusa and Laika like the garden :)
5 Correct 11 ms 616 KB Correct! Azusa and Laika like the garden :)
6 Correct 10 ms 828 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
8 Correct 8 ms 716 KB Correct! Azusa and Laika like the garden :)
9 Correct 11 ms 844 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
11 Correct 14 ms 820 KB Correct! Azusa and Laika like the garden :)
12 Correct 9 ms 844 KB Correct! Azusa and Laika like the garden :)
13 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
14 Correct 9 ms 736 KB Correct! Azusa and Laika like the garden :)
15 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
16 Correct 10 ms 828 KB Correct! Azusa and Laika like the garden :)
17 Correct 9 ms 756 KB Correct! Azusa and Laika like the garden :)
18 Correct 8 ms 688 KB Correct! Azusa and Laika like the garden :)
19 Correct 3 ms 452 KB Correct! Azusa and Laika like the garden :)
20 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
21 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
22 Correct 5 ms 588 KB Correct! Azusa and Laika like the garden :)
23 Correct 6 ms 668 KB Correct! Azusa and Laika like the garden :)
24 Correct 3 ms 576 KB Correct! Azusa and Laika like the garden :)
25 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
26 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
27 Correct 5 ms 588 KB Correct! Azusa and Laika like the garden :)
28 Correct 4 ms 612 KB Correct! Azusa and Laika like the garden :)
29 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
30 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
31 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
32 Correct 4 ms 580 KB Correct! Azusa and Laika like the garden :)
33 Correct 3 ms 572 KB Correct! Azusa and Laika like the garden :)
34 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
35 Correct 4 ms 588 KB Correct! Azusa and Laika like the garden :)
36 Correct 13 ms 972 KB Correct! Azusa and Laika like the garden :)
37 Correct 13 ms 964 KB Correct! Azusa and Laika like the garden :)
38 Correct 13 ms 904 KB Correct! Azusa and Laika like the garden :)
39 Correct 14 ms 1040 KB Correct! Azusa and Laika like the garden :)
40 Correct 14 ms 968 KB Correct! Azusa and Laika like the garden :)
41 Correct 14 ms 972 KB Correct! Azusa and Laika like the garden :)
42 Correct 13 ms 972 KB Correct! Azusa and Laika like the garden :)
43 Correct 17 ms 960 KB Correct! Azusa and Laika like the garden :)
44 Correct 13 ms 972 KB Correct! Azusa and Laika like the garden :)
45 Correct 12 ms 972 KB Correct! Azusa and Laika like the garden :)
46 Correct 13 ms 1068 KB Correct! Azusa and Laika like the garden :)
47 Correct 14 ms 932 KB Correct! Azusa and Laika like the garden :)
48 Correct 14 ms 948 KB Correct! Azusa and Laika like the garden :)
49 Correct 13 ms 1020 KB Correct! Azusa and Laika like the garden :)
50 Correct 14 ms 984 KB Correct! Azusa and Laika like the garden :)
51 Correct 13 ms 948 KB Correct! Azusa and Laika like the garden :)
52 Correct 13 ms 984 KB Correct! Azusa and Laika like the garden :)
53 Correct 13 ms 936 KB Correct! Azusa and Laika like the garden :)
54 Correct 13 ms 972 KB Correct! Azusa and Laika like the garden :)
55 Correct 14 ms 972 KB Correct! Azusa and Laika like the garden :)
56 Correct 14 ms 1088 KB Correct! Azusa and Laika like the garden :)
57 Correct 13 ms 1020 KB Correct! Azusa and Laika like the garden :)
58 Correct 13 ms 972 KB Correct! Azusa and Laika like the garden :)
59 Correct 14 ms 972 KB Correct! Azusa and Laika like the garden :)
60 Correct 14 ms 972 KB Correct! Azusa and Laika like the garden :)