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

• 問題: No.3744 XY Tiling
• ユーザー: 👑 kencho
• 提出日時: 2026-08-16 00:42:59
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 4,829 bytes
• コンパイル時間: 2,606 ms
• コンパイル使用メモリ: 351,476 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 12:38:54
• 合計ジャッジ時間: 6,021 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

サブタスク	配点	結果
部分点	60 %	AC * 19
満点	40 %	AC * 60
合計	5 * 100% = 500 点

ソースコード

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

struct Solution {
    int C;
    vector<vector<int>> color;
    vector<string> dir;
};

Solution transpose(Solution s) {
    int H = s.color.size(), W = s.color[0].size();
    Solution t{s.C, vector(W, vector<int>(H)), vector<string>(W, string(H, '?'))};
    string from = "><v^", to = "v^><";
    for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) {
        t.color[c][r] = s.color[r][c];
        t.dir[c][r] = to[from.find(s.dir[r][c])];
    }
    return t;
}

Solution small(int H, int W) {
    int C = H == 1 ? W / 2 + 1 : H == 2 ? 2 : H == 3 ? (W + 3) / 4 + 2 : 3;
    if (H == 5 && W >= 10) C = 4;
    Solution s{C, vector(H, vector<int>(W)), vector<string>(H, string(W, '?'))};
    auto horizontal = [&](int r) {
        for (int c = 0; c < W; c += 2) s.dir[r][c] = '>', s.dir[r][c + 1] = '<';
    };
    auto vertical = [&](int r) {
        for (int c = 0; c < W; ++c) s.dir[r][c] = 'v', s.dir[r + 1][c] = '^';
    };

    if (H == 1) {
        for (int c = 0; c < W; ++c) s.color[0][c] = (c + 1) / 2;
        horizontal(0);
    } else if (H == 2) {
        fill(s.color[1].begin(), s.color[1].end(), 1);
        vertical(0);
    } else if (H == 3) {
        fill(s.color[1].begin(), s.color[1].end(), 1);
        for (int c = 0; c < W; ++c)
            s.color[2][c] = c % 4 == 0 || c % 4 == 3 ? 1 : 2 + c / 4;
        vertical(0);
        horizontal(2);
    } else if (H == 4) {
        fill(s.color[1].begin(), s.color[1].end(), 1);
        fill(s.color[2].begin(), s.color[2].end(), 1);
        fill(s.color[3].begin(), s.color[3].end(), 2);
        vertical(0);
        vertical(2);
    } else if (W == 6 || W == 8) {
        vector<string> a = W == 6
            ? vector<string>{"122223", "121123", "122123", "111123", "222223"}
            : vector<string>{"12222223", "12111123", "12211223", "11111123", "22222223"};
        for (int r = 0; r < H; ++r)
            for (int c = 0; c < W; ++c) s.color[r][c] = a[r][c] - '1';
        horizontal(0);
        for (int c = 2; c < W - 2; ++c) s.dir[0][c] = 'v', s.dir[1][c] = '^';
        s.dir[1][0] = '>'; s.dir[1][1] = '<';
        s.dir[1][W - 2] = '>'; s.dir[1][W - 1] = '<';
        horizontal(2);
        for (int c = 0; c < W - 2; ++c) s.dir[3][c] = 'v', s.dir[4][c] = '^';
        s.dir[3][W - 2] = '>'; s.dir[3][W - 1] = '<';
        s.dir[4][W - 2] = '>'; s.dir[4][W - 1] = '<';
    } else {
        fill(s.color[0].begin(), s.color[0].end(), 0);
        fill(s.color[1].begin(), s.color[1].end(), 1);
        for (int c = 0; c < W; ++c) s.color[2][c] = 1 + c % 2;
        fill(s.color[3].begin(), s.color[3].end(), 2);
        fill(s.color[4].begin(), s.color[4].end(), 3);
        vertical(0);
        horizontal(2);
        vertical(3);
    }
    return s;
}

Solution large(int H, int W) {
    Solution s{3, vector(H, vector<int>(W)), vector<string>(H, string(W, '?'))};
    int A = 0, B = 1, C = 2;
    fill(s.color[0].begin(), s.color[0].end(), A); s.color[0][W - 1] = B;
    fill(s.color[1].begin(), s.color[1].end(), B); s.color[1][W - 2] = A;
    fill(s.color[2].begin(), s.color[2].end(), B); s.color[2][1] = s.color[2][W - 2] = A;
    fill(s.color[3].begin(), s.color[3].end(), A); s.color[3][0] = s.color[3][W - 1] = B;
    for (int r = 4; r <= H - 3; ++r) {
        for (int c = 0; c < W - 2; ++c) s.color[r][c] = c % 2 ? A : B;
        s.color[r][W - 2] = A; s.color[r][W - 1] = B;
    }
    fill(s.color[H - 2].begin(), s.color[H - 2].end(), B);
    fill(s.color[H - 1].begin(), s.color[H - 1].end(), C);

    for (int c = 0; c < W - 2; ++c) s.dir[0][c] = 'v', s.dir[1][c] = '^';
    for (int r = 0; r < 4; ++r)
        s.dir[r][W - 2] = '>', s.dir[r][W - 1] = '<';
    s.dir[2][0] = '>'; s.dir[2][1] = '<';
    s.dir[3][0] = '>'; s.dir[3][1] = '<';
    for (int c = 2; c < W - 2; ++c) s.dir[2][c] = 'v', s.dir[3][c] = '^';
    for (int r = 4; r <= H - 3; ++r)
        for (int c = 0; c < W; c += 2) s.dir[r][c] = '>', s.dir[r][c + 1] = '<';
    for (int c = 0; c < W; ++c) s.dir[H - 2][c] = 'v', s.dir[H - 1][c] = '^';
    return s;
}

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

    int H, W;
    cin >> H >> W;
    bool swapped = H > W;
    int h = min(H, W), w = max(H, W);
    Solution ans;
    if (h <= 5) ans = small(h, w);
    else if (w % 2 == 0) ans = large(h, w);
    else ans = transpose(large(w, h));
    if (swapped) ans = transpose(ans);

    cout << ans.C << '\n';
    for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) {
        if (ans.dir[r][c] != '>' && ans.dir[r][c] != 'v') continue;
        int nr = r + (ans.dir[r][c] == 'v');
        int nc = c + (ans.dir[r][c] == '>');
        cout << r + 1 << ' ' << c + 1 << ' ' << ans.color[r][c] + 1 << ' '
             << nr + 1 << ' ' << nc + 1 << ' ' << ans.color[nr][nc] + 1 << '\n';
    }
}