Submission #520379

#	Time	Username	Problem	Language	Result	Execution time	Memory
520379		Alex_tz307	Gardening (RMI21_gardening)	C++17	100 / 100	24 ms	1088 KiB

Main

#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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22