#1187652 (C++23) No.3744 XY Tiling

• 問題: No.3744 XY Tiling
• ユーザー: uruzunyaa
• 提出日時: 2026-09-18 22:29:48
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: RE
• 実行時間: -
• コード長: 4,821 bytes
• コンパイル時間: 2,435 ms
• コンパイル使用メモリ: 365,540 KB
• 実行使用メモリ: 10,052 KB
• 最終ジャッジ日時: 2026-09-19 13:24:34
• 合計ジャッジ時間: 8,886 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge6_0

サブタスク	配点	結果
部分点	60 %	AC * 19
満点	40 %	AC * 25 RE * 35
合計	5 * 60% = 300 点

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Domino {
    int x1, y1, x2, y2;
};

enum Type {
    UP,
    DOWN,
    LEFT,
    RIGHT
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    // H = 2
    if (H == 2) {
        cout << 2 << '\n';

        for (int j = 0; j < W; j++) {
            cout << 1 << ' ' << j + 1 << ' ' << 1 << ' '
                 << 2 << ' ' << j + 1 << ' ' << 2 << '\n';
        }

        return 0;
    }

    // W = 2
    if (W == 2) {
        cout << 2 << '\n';

        for (int i = 0; i < H; i++) {
            cout << i + 1 << ' ' << 1 << ' ' << 1 << ' '
                 << i + 1 << ' ' << 2 << ' ' << 2 << '\n';
        }

        return 0;
    }

    // ここから H,W >= 4 の偶数。
    int h = H / 2;
    int w = W / 2;

    vector<vector<Type>> type(h, vector<Type>(w));

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (j == w - 1) {
                // 一番右は全部 L
                type[i][j] = LEFT;
            } else if (i == 0) {
                // 一番上
                type[i][j] = UP;
            } else if (i == h - 1) {
                // 一番下
                type[i][j] = DOWN;
            } else if (i == 1) {
                // 上から2段目
                if (j == 0) type[i][j] = RIGHT;
                else        type[i][j] = DOWN;
            } else {
                // 中間部分
                if (j == 0) type[i][j] = RIGHT;
                else        type[i][j] = LEFT;
            }
        }
    }

    // is_two[i][j] = 色2にするマス
    vector<vector<bool>> is_two(H, vector<bool>(W, false));

    vector<Domino> dominoes;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int r = 2 * i;
            int c = 2 * j;

            if (type[i][j] == UP) {
                // 22
                // ..
                is_two[r][c] = true;
                is_two[r][c + 1] = true;

                dominoes.push_back({r, c, r + 1, c});
                dominoes.push_back({r, c + 1, r + 1, c + 1});
            }

            if (type[i][j] == DOWN) {
                // ..
                // 22
                is_two[r + 1][c] = true;
                is_two[r + 1][c + 1] = true;

                dominoes.push_back({r, c, r + 1, c});
                dominoes.push_back({r, c + 1, r + 1, c + 1});
            }

            if (type[i][j] == LEFT) {
                // 2.
                // 2.
                is_two[r][c] = true;
                is_two[r + 1][c] = true;

                dominoes.push_back({r, c, r, c + 1});
                dominoes.push_back({r + 1, c, r + 1, c + 1});
            }

            if (type[i][j] == RIGHT) {
                // .2
                // .2
                is_two[r][c + 1] = true;
                is_two[r + 1][c + 1] = true;

                dominoes.push_back({r, c, r, c + 1});
                dominoes.push_back({r + 1, c, r + 1, c + 1});
            }
        }
    }

    vector<vector<int>> color(H, vector<int>(W, 0));

    // 色2
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (is_two[i][j]) {
                color[i][j] = 2;
            }
        }
    }

    // 色2以外はちょうど2連結成分。
    // それぞれ色1、色3にする。
    int component_count = 0;

    const int dx[] = {1, -1, 0, 0};
    const int dy[] = {0, 0, 1, -1};

    for (int si = 0; si < H; si++) {
        for (int sj = 0; sj < W; sj++) {
            if (is_two[si][sj]) continue;
            if (color[si][sj] != 0) continue;

            assert(component_count < 2);

            int c = (component_count == 0 ? 1 : 3);
            component_count++;

            queue<pair<int, int>> que;
            que.push({si, sj});
            color[si][sj] = c;

            while (!que.empty()) {
                auto [x, y] = que.front();
                que.pop();

                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];

                    if (nx < 0 || nx >= H) continue;
                    if (ny < 0 || ny >= W) continue;
                    if (is_two[nx][ny]) continue;
                    if (color[nx][ny] != 0) continue;

                    color[nx][ny] = c;
                    que.push({nx, ny});
                }
            }
        }
    }

    assert(component_count == 2);
    assert((int)dominoes.size() == H * W / 2);

    cout << 3 << '\n';

    for (auto d : dominoes) {
        cout << d.x1 + 1 << ' '
             << d.y1 + 1 << ' '
             << color[d.x1][d.y1] << ' '
             << d.x2 + 1 << ' '
             << d.y2 + 1 << ' '
             << color[d.x2][d.y2] << '\n';
    }

    return 0;
}