#1187895 (C++23) No.3742 Re: Verse X

• 問題: No.3742 Re: Verse X
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 03:50:54
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 50 ms / 2,000 ms
• コード長: 12,458 bytes
• コンパイル時間: 4,038 ms
• コンパイル使用メモリ: 367,420 KB
• 実行使用メモリ: 11,996 KB
• 最終ジャッジ日時: 2026-09-19 13:26:18
• 合計ジャッジ時間: 7,926 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 57

ソースコード

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

struct Op {
    int k, r, c; // r,c は 0-indexed
};

// 左上付近の「2層目の (1,2) だけ」を反転する
const vector<Op> Q_TOP = {
    {3,3,4},
    {1,1,6},
    {1,6,1}
};

// 左上付近の「2層目の (2,1) だけ」を反転する
const vector<Op> Q_LEFT = {
    {3,4,3},
    {1,1,6},
    {1,6,1}
};

// 最外周の (0,0),(0,2),(2,0) を反転する
const vector<Op> CORNER = {
    {1,1,3},
    {1,1,5},
    {1,2,2},
    {1,3,1},
    {1,5,1},
    {3,3,3}
};

// 最外周の (0,1),(0,3) を反転する
const vector<Op> P1 = {
    {1,1,4},
    {1,1,6},
    {1,2,1},
    {1,2,5},
    {1,4,1},
    {1,5,2},
    {1,6,1},
    {3,3,4},
    {3,4,3}
};

// 最外周の (0,2),(0,4) を反転する
const vector<Op> P2 = {
    {1,1,5},
    {1,1,7},
    {1,2,4},
    {3,3,5}
};

// 最外周の (0,3),(0,5) を反転する
const vector<Op> P3 = {
    {1,1,2},
    {1,1,6},
    {1,3,2},
    {1,5,2},
    {3,3,4}
};

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

    int N;
    cin >> N;

    vector<string> S(N);
    for (auto& s : S) cin >> s;

    vector<vector<int>> a(N, vector<int>(N));

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            a[r][c] = (S[r][c] == '#');
        }
    }

    auto cells_of = [&](const Op& op) {
        vector<pair<int,int>> cells;

        for (int d = -op.k; d <= op.k; d++) {
            cells.push_back({op.r + d, op.c + d});

            if (d != 0) {
                cells.push_back({op.r + d, op.c - d});
            }
        }

        return cells;
    };

    // ============================================================
    // N <= 10
    // 小さいので盤面全体を GF(2) ガウス消去
    // ============================================================

    if (N <= 10) {
        constexpr int B = 128;

        vector<Op> ops;
        vector<bitset<B>> vecs;

        for (int k = 1; 2 * k + 1 <= N; k++) {
            for (int r = k; r + k < N; r++) {
                for (int c = k; c + k < N; c++) {
                    Op op{k, r, c};

                    bitset<B> v;

                    for (auto [x, y] : cells_of(op)) {
                        v.set(x * N + y);
                    }

                    ops.push_back(op);
                    vecs.push_back(v);
                }
            }
        }

        int D = N * N;
        int M = ops.size();

        array<bitset<B>, B> basis_v;
        array<bitset<B>, B> basis_c;
        array<bool, B> has{};

        for (int i = 0; i < M; i++) {
            bitset<B> v = vecs[i];
            bitset<B> c;

            c.set(i);

            for (int p = 0; p < D; p++) {
                if (!v[p]) continue;

                if (has[p]) {
                    v ^= basis_v[p];
                    c ^= basis_c[p];
                }
                else {
                    has[p] = true;
                    basis_v[p] = v;
                    basis_c[p] = c;
                    break;
                }
            }
        }

        bitset<B> target;

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (a[r][c]) {
                    target.set(r * N + c);
                }
            }
        }

        bitset<B> comb;

        for (int p = 0; p < D; p++) {
            if (!target[p]) continue;

            if (!has[p]) {
                cout << -1 << '\n';
                return 0;
            }

            target ^= basis_v[p];
            comb ^= basis_c[p];
        }

        vector<Op> ans;

        for (int i = 0; i < M; i++) {
            if (comb[i]) {
                ans.push_back(ops[i]);
            }
        }

        cout << ans.size() << '\n';

        for (auto [k, r, c] : ans) {
            cout << k << ' ' << r + 1 << ' ' << c + 1 << '\n';
        }

        return 0;
    }

    // ============================================================
    // N >= 11
    // ============================================================

    // 4辺 × 市松模様2色 = 8個の不変量
    for (int p = 0; p < 2; p++) {
        int x = 0;

        // 上辺
        for (int c = p; c < N; c += 2) {
            x ^= a[0][c];
        }

        if (x) {
            cout << -1 << '\n';
            return 0;
        }

        // 下辺
        x = 0;

        for (int c = p; c < N; c += 2) {
            x ^= a[N - 1][c];
        }

        if (x) {
            cout << -1 << '\n';
            return 0;
        }

        // 左辺
        x = 0;

        for (int r = p; r < N; r += 2) {
            x ^= a[r][0];
        }

        if (x) {
            cout << -1 << '\n';
            return 0;
        }

        // 右辺
        x = 0;

        for (int r = p; r < N; r += 2) {
            x ^= a[r][N - 1];
        }

        if (x) {
            cout << -1 << '\n';
            return 0;
        }
    }

    // 同じ操作を2回行ったら打ち消し合うので、
    // 各操作を使う回数の偶奇だけ管理する。
    vector<vector<array<unsigned char, 4>>> used(
        N,
        vector<array<unsigned char, 4>>(N)
    );

    auto apply_op = [&](const Op& op) {
        used[op.r][op.c][op.k] ^= 1;

        for (int d = -op.k; d <= op.k; d++) {
            a[op.r + d][op.c + d] ^= 1;

            if (d != 0) {
                a[op.r + d][op.c - d] ^= 1;
            }
        }
    };

    auto transform_op = [&](Op op,
                            bool flip_r,
                            bool flip_c,
                            bool transpose) {
        if (transpose) {
            swap(op.r, op.c);
        }

        if (flip_r) {
            op.r = N - 1 - op.r;
        }

        if (flip_c) {
            op.c = N - 1 - op.c;
        }

        return op;
    };

    auto transform_gadget = [&](const vector<Op>& g,
                                bool flip_r,
                                bool flip_c,
                                bool transpose) {
        vector<Op> res;

        for (auto op : g) {
            res.push_back(
                transform_op(op, flip_r, flip_c, transpose)
            );
        }

        return res;
    };

    auto apply_gadget = [&](const vector<Op>& g) {
        for (auto op : g) {
            apply_op(op);
        }
    };

    // ============================================================
    // 1. 外から2層目を全部白にする
    // ============================================================

    // 角付近の例外8マス
    set<pair<int,int>> special;

    for (int fr = 0; fr < 2; fr++) {
        for (int fc = 0; fc < 2; fc++) {
            int r1 = fr ? N - 2 : 1;
            int c1 = fc ? N - 3 : 2;

            special.insert({r1, c1});

            int r2 = fr ? N - 3 : 2;
            int c2 = fc ? N - 2 : 1;

            special.insert({r2, c2});
        }
    }

    // 例外以外の2層目は、中心に k=1 を置けば
    // 2層目の中ではそのマスだけが反転する。
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            int d = min({
                r,
                c,
                N - 1 - r,
                N - 1 - c
            });

            if (d != 1) continue;
            if (special.count({r, c})) continue;

            if (a[r][c]) {
                apply_op({1, r, c});
            }
        }
    }

    // 角付近の例外8マスを消す
    for (int fr = 0; fr < 2; fr++) {
        for (int fc = 0; fc < 2; fc++) {
            int r1 = fr ? N - 2 : 1;
            int c1 = fc ? N - 3 : 2;

            if (a[r1][c1]) {
                apply_gadget(
                    transform_gadget(
                        Q_TOP,
                        fr,
                        fc,
                        false
                    )
                );
            }

            int r2 = fr ? N - 3 : 2;
            int c2 = fc ? N - 2 : 1;

            if (a[r2][c2]) {
                apply_gadget(
                    transform_gadget(
                        Q_LEFT,
                        fr,
                        fc,
                        false
                    )
                );
            }
        }
    }

    // ============================================================
    // 2. 最外周の四隅を白にする
    // ============================================================

    for (int fr = 0; fr < 2; fr++) {
        for (int fc = 0; fc < 2; fc++) {
            int r = fr ? N - 1 : 0;
            int c = fc ? N - 1 : 0;

            if (a[r][c]) {
                apply_gadget(
                    transform_gadget(
                        CORNER,
                        fr,
                        fc,
                        false
                    )
                );
            }
        }
    }

    // 上辺の (0,j),(0,j+2) だけを反転する gadget
    auto top_pair_gadget = [&](int j) {
        if (j == 1) {
            return P1;
        }

        if (j == 2) {
            return P2;
        }

        if (j == 3) {
            return P3;
        }

        if (4 <= j && j <= N - 7) {
            return vector<Op>{
                {3,3,j + 1},
                {1,1,j - 1},
                {1,1,j + 3}
            };
        }

        if (j == N - 6) {
            return transform_gadget(
                P3,
                false,
                true,
                false
            );
        }

        if (j == N - 5) {
            return transform_gadget(
                P2,
                false,
                true,
                false
            );
        }

        return transform_gadget(
            P1,
            false,
            true,
            false
        );
    };

    struct SideTransform {
        bool flip_r;
        bool flip_c;
        bool transpose;
    };

    vector<SideTransform> sides = {
        // 上
        {false, false, false},

        // 下
        {true, false, false},

        // 左
        {false, false, true},

        // 右
        {false, true, true}
    };

    auto transform_point = [&](int r,
                               int c,
                               SideTransform t) {
        if (t.transpose) {
            swap(r, c);
        }

        if (t.flip_r) {
            r = N - 1 - r;
        }

        if (t.flip_c) {
            c = N - 1 - c;
        }

        return pair<int,int>{r, c};
    };

    // ============================================================
    // 3. 最外周を2マスずつ右へ送る要領で消す
    // ============================================================

    for (auto st : sides) {
        for (int j = 1; j <= N - 4; j++) {
            auto [r, c] =
                transform_point(0, j, st);

            if (!a[r][c]) continue;

            auto g = top_pair_gadget(j);

            apply_gadget(
                transform_gadget(
                    g,
                    st.flip_r,
                    st.flip_c,
                    st.transpose
                )
            );
        }
    }

    // ============================================================
    // 4. 残った内部を1マス反転 gadget で消す
    //
    // X_2(r,c)
    // xor X_1(r-1,c-1)
    // xor X_1(r-1,c+1)
    // xor X_1(r+1,c-1)
    // xor X_1(r+1,c+1)
    //
    // で (r,c) だけを反転する。
    // ============================================================

    for (int r = 2; r <= N - 3; r++) {
        for (int c = 2; c <= N - 3; c++) {
            if (!a[r][c]) continue;

            apply_op({2, r, c});

            apply_op({1, r - 1, c - 1});
            apply_op({1, r - 1, c + 1});
            apply_op({1, r + 1, c - 1});
            apply_op({1, r + 1, c + 1});
        }
    }

    // ============================================================
    // 同じ操作を偶数回使ったものを相殺して出力
    // ============================================================

    vector<Op> ans;

    for (int k = 1; k <= 3; k++) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (used[r][c][k]) {
                    ans.push_back({k, r, c});
                }
            }
        }
    }

    cout << ans.size() << '\n';

    for (auto [k, r, c] : ans) {
        cout
            << k << ' '
            << r + 1 << ' '
            << c + 1 << '\n';
    }
}