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

• 問題: No.3742 Re: Verse X
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 03:05:21
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 97 ms / 2,000 ms
• コード長: 7,092 bytes
• コンパイル時間: 2,402 ms
• コンパイル使用メモリ: 357,368 KB
• 実行使用メモリ: 18,624 KB
• 最終ジャッジ日時: 2026-09-19 13:26:14
• 合計ジャッジ時間: 7,749 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge5_0

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

ソースコード

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

static constexpr int MAXD = 4100;
using Bits = bitset<MAXD>;

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

struct XorBasis {
    int dim;

    // vec[p] : pivot p を持つベクトル
    // comb[p]: vec[p] を作る元操作の XOR
    vector<Bits> vec, comb;
    vector<char> has;

    // 独立だった元操作だけ保存
    vector<Op> raw;

    XorBasis(int d)
        : dim(d), vec(d), comb(d), has(d, 0) {}

    void add(Bits v, Op op) {
        Bits c;

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

            if (has[p]) {
                v ^= vec[p];
                c ^= comb[p];
            } else {
                int id = (int)raw.size();

                c.set(id);

                has[p] = 1;
                vec[p] = v;
                comb[p] = c;
                raw.push_back(op);
                return;
            }
        }
    }

    optional<vector<Op>> solve(Bits t) const {
        Bits c;

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

            if (!has[p]) return nullopt;

            t ^= vec[p];
            c ^= comb[p];
        }

        vector<Op> ret;

        for (int i = 0; i < (int)raw.size(); ++i) {
            if (c[i]) ret.push_back(raw[i]);
        }

        return ret;
    }
};

void apply_op(vector<vector<int>>& a, Op op) {
    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;
        }
    }
}

Bits full_vec(int N, Op op) {
    Bits v;

    for (int d = -op.k; d <= op.k; ++d) {
        v.set((op.r + d) * N + (op.c + d));

        if (d != 0) {
            v.set((op.r + d) * N + (op.c - d));
        }
    }

    return v;
}

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] == '#');
        }
    }

    // -----------------------------
    // N <= 9 : 全盤面を直接ガウス消去
    // -----------------------------
    if (N < 10) {
        XorBasis bs(N * N);

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

        Bits target;

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

        auto ans = bs.solve(target);

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

        cout << ans->size() << '\n';

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

        return 0;
    }

    // -----------------------------
    // 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<int>> id(N, vector<int>(N, -1));
    vector<pair<int, int>> pos;

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (
                r < 2 || r >= N - 2 ||
                c < 2 || c >= N - 2
            ) {
                id[r][c] = (int)pos.size();
                pos.push_back({r, c});
            }
        }
    }

    int D = (int)pos.size(); // 8N-16

    auto boundary_vec = [&](Op op) {
        Bits v;

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

            if (id[r][c] != -1) {
                v.set(id[r][c]);
            }

            if (d != 0) {
                c = op.c - d;

                if (id[r][c] != -1) {
                    v.set(id[r][c]);
                }
            }
        }

        return v;
    };

    XorBasis bs(D);

    // -----------------------------
    // k=1,3 のうち、外側2層に触れるもの
    // -----------------------------
    for (int k : {1, 3}) {
        for (int r = k; r < N - k; ++r) {
            for (int c = k; c < N - k; ++c) {

                if (
                    r <= k + 1 ||
                    r >= N - k - 2 ||
                    c <= k + 1 ||
                    c >= N - k - 2
                ) {
                    Op op{k, r, c};
                    bs.add(boundary_vec(op), op);
                }
            }
        }
    }

    Bits target;

    for (int i = 0; i < D; ++i) {
        auto [r, c] = pos[i];

        if (a[r][c]) {
            target.set(i);
        }
    }

    auto bd = bs.solve(target);

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

    vector<Op> ans = *bd;

    // 境界を実際に消して、
    // 残った内部の状態を知る
    for (auto op : *bd) {
        apply_op(a, op);
    }

    // -----------------------------
    // 内部を 1 マス反転 gadget で消す
    //
    // X2(r,c)
    // xor X1(r-1,c-1)
    // xor X1(r-1,c+1)
    // xor X1(r+1,c-1)
    // xor X1(r+1,c+1)
    //
    // = (r,c) だけ反転
    // -----------------------------

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

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

            ans.push_back({2, r, c});

            use1[r - 1][c - 1] ^= 1;
            use1[r - 1][c + 1] ^= 1;
            use1[r + 1][c - 1] ^= 1;
            use1[r + 1][c + 1] ^= 1;
        }
    }

    // 同一 k=1 操作は偶数回なら消える
    for (int r = 1; r <= N - 2; ++r) {
        for (int c = 1; c <= N - 2; ++c) {
            if (use1[r][c]) {
                ans.push_back({1, r, c});
            }
        }
    }

    // 最大
    // (8N-24) + (N-4)^2 + (N-2)^2
    // = 2N^2 - 4N - 4
    // <= 497996

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

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