#1187854 (C++23(gcc16)) No.2958 Placing Many L-s

• 問題: No.2958 Placing Many L-s
• ユーザー: simasima_71
• 提出日時: 2026-09-19 01:29:26
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 111 ms / 2,000 ms
• コード長: 5,862 bytes
• コンパイル時間: 6,466 ms
• コンパイル使用メモリ: 406,860 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 01:29:36
• 合計ジャッジ時間: 8,259 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 29

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <regex>
using mint=modint998244353;

//グリッド構築24題対策ライブラリ

using Board = std::vector<std::vector<int>>;

// Rotations allowed; reflections forbidden. n,m must be positive.
// Returns nullopt exactly when no tiling exists.
// Time O(n*m), space O(n*m), including the returned board.
inline std::optional<Board> tileTetromino(int n, int m, char type) {
    if (n <= 0 || m <= 0)
        throw std::invalid_argument("n and m must be positive");
    if (std::string("STZIOLJ").find(type) == std::string::npos)
        throw std::invalid_argument("Unknown tetromino type");

    const long long area = 1LL * n * m;
    bool possible = false;
    switch (type) {
        case 'I': possible = n % 4 == 0 || m % 4 == 0; break;
        case 'O': possible = n % 2 == 0 && m % 2 == 0; break;
        case 'T': possible = n % 4 == 0 && m % 4 == 0; break;
        case 'L': case 'J':
            possible = area % 8 == 0 && n != 1 && n != 3
                                      && m != 1 && m != 3;
            break;
        case 'S': case 'Z': break;
    }
    if (!possible) return std::nullopt;
    if (area / 4 > std::numeric_limits<int>::max())
        throw std::length_error("Tile IDs do not fit in int");

    int h = n, w = m;
    bool rotate = false;
    if (type == 'L' || type == 'J') {
        // Even case: w is divisible by 4.
        // Odd case: h is odd, w is divisible by 8.
        if ((h % 2 == 0 && w % 2 == 0 && w % 4 != 0) ||
            (h % 2 == 0 && w % 2 != 0)) {
            std::swap(h, w);
            rotate = true;
        }
    }

    Board ans(n, std::vector<int>(m));
    int offset = 0;
    auto put = [&](int r, int c, const Board& p, int count) {
        for (int i = 0; i < static_cast<int>(p.size()); ++i) {
            for (int j = 0; j < static_cast<int>(p[i].size()); ++j) {
                // Rotate the entire virtual board by 90 degrees if needed.
                int rr = rotate ? c + j : r + i;
                int cc = rotate ? m - 1 - (r + i) : c + j;
                // Reflect an all-L tiling to obtain an all-J tiling.
                if (type == 'J') cc = m - 1 - cc;
                ans[rr][cc] = offset + p[i][j];
            }
        }
        offset += count;
    };

    if (type == 'I' || type == 'O' || type == 'T') {
        Board p;
        int count;
        if (type == 'I') {
            p = (m % 4 == 0) ? Board{{1, 1, 1, 1}}
                             : Board{{1}, {1}, {1}, {1}};
            count = 1;
        } else if (type == 'O') {
            p = {{1, 1}, {1, 1}};
            count = 1;
        } else {
            p = {{1, 1, 1, 2},
                 {3, 1, 2, 2},
                 {3, 3, 4, 2},
                 {3, 4, 4, 4}};
            count = 4;
        }
        int ph = static_cast<int>(p.size());
        int pw = static_cast<int>(p[0].size());
        for (int r = 0; r < h; r += ph)
            for (int c = 0; c < w; c += pw)
                put(r, c, p, count);
    } else {
        const Board p2 = {{1, 1, 1, 2},
                          {1, 2, 2, 2}};
        const Board p5 = {{1, 1, 1, 5, 6, 2, 2, 2},
                          {1, 5, 5, 5, 6, 2, 3, 3},
                          {10, 9, 9, 9, 6, 6, 4, 3},
                          {10, 9, 8, 8, 8, 7, 4, 3},
                          {10, 10, 8, 7, 7, 7, 4, 4}};
        int start = 0;
        if (h % 2 != 0) {
            for (int c = 0; c < w; c += 8)
                put(0, c, p5, 10);
            start = 5;
        }
        for (int r = start; r < h; r += 2)
            for (int c = 0; c < w; c += 4)
                put(r, c, p2, 2);
    }
    return ans;
}

// 回転・裏返しを許可する版。
// 前の tileTetromino が定義されていることが必要。
// 時間・空間計算量：O(n*m)
inline std::optional<Board> tileTetrominoWithReflection(
    int n, int m, char type
) {
    // L・J以外、または辺の長さに3がない場合は前の関数でよい。
    if ((type != 'L' && type != 'J') || (n != 3 && m != 3)) {
        return tileTetromino(n, m, type);
    }

    if (n <= 0 || m <= 0) {
        throw std::invalid_argument("n and m must be positive");
    }

    // 3 × length の長方形として構成する。
    const int length = (n == 3 ? m : n);
    if (length % 8 != 0) {
        return std::nullopt;
    }

    const int pattern[3][8] = {
        {1, 1, 2, 2, 2, 3, 4, 4},
        {1, 5, 2, 3, 3, 3, 6, 4},
        {1, 5, 5, 5, 6, 6, 6, 4}
    };

    Board ans(n, std::vector<int>(m));
    int offset = 0;

    for (int start = 0; start < length; start += 8) {
        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 8; ++c) {
                int id = offset + pattern[r][c];

                if (n == 3) {
                    ans[r][start + c] = id;
                } else {
                    ans[start + c][r] = id;
                }
            }
        }
        offset += 6;
    }

    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll tt;
    cin>>tt;
    rep(iaa,0,tt){
    ll n,m;
    cin>>n>>m;
    auto u=tileTetrominoWithReflection(n,m,'L');
    if(!u){
        cout<<-1<<endl;
        continue;
    }
    const auto& board = *u;
    cout<<n*m/4<<endl;
    rep(i,0,board.size()){
        rep(j,0,board[i].size()){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
}
}