結果

問題 No.3335 ReCT
コンテスト
ユーザー Kude
提出日時 2025-11-08 12:38:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 214 ms / 2,000 ms
コード長 4,552 bytes
コンパイル時間 4,438 ms
コンパイル使用メモリ 314,688 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-08 12:39:15
合計ジャッジ時間 18,603 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 97
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = unsigned __int128;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  constexpr int M = 11;
  VL cs[M][M], ts[M][M];
  rep(si, M) rep(sj, M) {
    int d[M][M]{};
    auto f = [&](auto&& reg) {
      rep(_, 4) {
        [&]() {
          ll bit = 0;
          int bi = -1, bj = -1;
          rrep(i, M) rrep(j, M) {
            if (d[i][j]) bit |= ll(1) << (i * M + j), bi = i, bj = j;
          }
          assert(bi != -1);
          reg[bi][bj].emplace_back(bit);
        }();
        int nd[M][M]{};
        rep(i, M) rep(j, M) nd[i][j] = d[M-1-j][i];
        memcpy(d, nd, sizeof(d));
      }
    };
    // c
    for (int l1 = 2; sj + l1 <= M; l1++) {
      for (int l2 = 3; si + l2 <= M; l2++) {
        for (int l3 = 2; sj + l3 <= M; l3++) {
          memset(d, 0, sizeof(d));
          rep(k, l1) d[si][sj+k] = 1;
          rep(k, l2) d[si+k][sj] = 1;
          rep(k, l3) d[si+l2-1][sj+k] = 1;
          f(cs);
        }
      }
    }
    // t
    for (int l1 = 2; sj - l1 + 1 >= 0; l1++) {
      for (int l2 = 2; sj + l2 <= M; l2++) {
        for (int l3 = 2; si + l3 <= M; l3++) {
          memset(d, 0, sizeof(d));
          rep(k, l1) d[si][sj-k] = 1;
          rep(k, l2) d[si][sj+k] = 1;
          rep(k, l3) d[si+k][sj] = 1;
          f(ts);
        }
      }
    }
  }
  auto find_sol = [&](int h, int w, int mode) -> VL& {
    static VL memo[M+1][M+1][4];
    static bool valid[M+1][M+1][4];
    if (valid[h][w][mode]) return memo[h][w][mode];
    vector<pair<ll, int>> trans[M][M];
    auto add = [&](auto&& src, auto&& dest, int label) {
      rep(i, h) rep(j, w) {
        for (ll b : src[i][j]) {
          bool ok = true;
          rep(i, M) rep(j, M) ok &= (i < h && j < w) || (~b >> (i * M + j) & 1);
          if (ok) dest[i][j].emplace_back(b, label);
        }
      }
    };
    if (mode & 1) add(cs, trans, 1);
    if (mode & 2) add(ts, trans, 2);
    VL sol;
    auto dfs = [&](auto&& self, int i, int j, ll used, int kinds) -> bool {
      if (j == w) i++, j = 0;
      if (i == h) return kinds == mode;
      if (used >> (i * M + j) & 1) {
        return self(self, i, j + 1, used, kinds);
      } else {
        for (auto [b, label] : trans[i][j]) if (!(b & used)) {
          sol.emplace_back(b);
          bool res = self(self, i, j + 1, used | b, kinds | label);
          if (res) return true;
          sol.pop_back();
        }
        return false;
      }
    };
    ll used = ~ll(0);
    rep(i, h) rep(j, w) used ^= ll(1) << (i * M + j);
    dfs(dfs, 0, 0, used, 0);
    valid[h][w][mode] = true;
    return memo[h][w][mode] = move(sol);
  };
  // int mode;
  // cin >> mode;
  // for (int h = 1; h <= M; h++) {
  //   for (int w = 1, w_last = h <= 3 ? M : h < 8 ? 8 : 3; w <= w_last; w++) {
  //     auto sol = find_sol(h, w, mode);
  //     bool res = !sol.empty();
  //     if (w == 1) cout << h << ": ";
  //     cout << res;
  //     if (w == w_last) cout << '\n';
  //   }
  // }
  int h, w;
  cin >> h >> w;
  VVI a(h, VI(w));
  for (int mode = 1; mode <= 3; mode++) {
    bool ok = mode == 1 ? min(h, w) >= 4 || (min(h, w) == 3 && max(h, w) % 2 == 0)
              : mode == 2 ? min(h, w) >= 4 || (min(h, w) == 3 && max(h, w) >= 6)
              : min(h, w) >= 3;
    if (!ok) {
      cout << -1 << '\n';
      continue;
    }
    int id = 0;
    for (int i = h; i;) {
      int hh = w == 3 ? (i >= 12 ? 6 : i) : (i >= 8 ? 4 : i);
      i -= hh;
      for (int j = w; j;) {
        int ww = hh == 3 ? (j >= 12 ? 6 : j) : (j >= 8 ? 4 : j);
        j -= ww;
        VL& sol = find_sol(hh, ww, mode);
        assert(!sol.empty());
        for (ll b : sol) {
          id++;
          rep(ii, hh) rep(jj, ww) if (b >> (ii * M + jj) & 1) a[i+ii][j+jj] = id;
        }
      }
    }
    cout << id << '\n';
    rep(i, h) rep(j, w) cout << a[i][j] << " \n"[j + 1 == w];
  }
}
0