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

• 問題: No.3742 Re: Verse X
• ユーザー: 👑 kencho
• 提出日時: 2026-09-19 08:22:39
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 3,819 bytes
• コンパイル時間: 2,318 ms
• コンパイル使用メモリ: 353,616 KB
• 実行使用メモリ: 100,604 KB
• 最終ジャッジ日時: 2026-09-19 13:30:40
• 合計ジャッジ時間: 10,184 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 32 TLE * 1 -- * 24

ソースコード

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

// 全ての合法な操作を列挙し、盤面全体に対して F_2 上の掃き出し法を行う。
// 操作数 Q = N(N-1)(N-2)/6、ベクトルの次元 D = N^2。
// 最悪計算量は O(Q D^2) = O(N^7)。大きな入力では TLE を想定する。
// ベクトルは非零成分の添字を昇順に保持し、密行列の一括確保を避ける。
// メモリ計算量の最悪上界は、復元用の記録を含めて O(D^2) = O(N^4)。

struct Operation {
    int k, r, c;
};

struct BasisRecord {
    vector<int> cells;
    Operation operation;
    vector<int> dependencies;
};

vector<int> xor_vectors(const vector<int>& a, const vector<int>& b) {
    vector<int> result;
    result.reserve(a.size() + b.size());
    set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
                             back_inserter(result));
    return result;
}

class LinearBasis {
    vector<int> pivot;
    vector<BasisRecord> records;

public:
    explicit LinearBasis(int dimension) : pivot(dimension, -1) {}

    void add(vector<int> cells, Operation operation) {
        vector<int> dependencies;
        while (!cells.empty()) {
            int position = cells.front();
            int id = pivot[position];
            if (id == -1) {
                pivot[position] = static_cast<int>(records.size());
                records.push_back({move(cells), operation, move(dependencies)});
                return;
            }
            cells = xor_vectors(cells, records[id].cells);
            dependencies.push_back(id);
        }
    }

    bool solve(vector<int> target, vector<Operation>& answer) const {
        vector<unsigned char> selected(records.size(), 0);
        while (!target.empty()) {
            int id = pivot[target.front()];
            if (id == -1) return false;
            target = xor_vectors(target, records[id].cells);
            selected[id] ^= 1;
        }

        // 各基底は、追加時の元の操作と、それ以前の基底の XOR である。
        // 逆順に展開して、実際に行う操作を復元する。
        for (int id = static_cast<int>(records.size()) - 1; id >= 0; --id) {
            if (!selected[id]) continue;
            answer.push_back(records[id].operation);
            for (int dependency : records[id].dependencies) {
                selected[dependency] ^= 1;
            }
        }
        return true;
    }
};

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> target;
    for (int r = 0; r < n; ++r) {
        string row;
        cin >> row;
        for (int c = 0; c < n; ++c) {
            if (row[c] == '#') target.push_back(r * n + c);
        }
    }

    LinearBasis basis(n * n);
    for (int k = 1; k <= (n - 1) / 2; ++k) {
        for (int r = k; r < n - k; ++r) {
            for (int c = k; c < n - k; ++c) {
                vector<int> cells;
                cells.reserve(4 * k + 1);
                for (int i = -k; i <= k; ++i) {
                    cells.push_back((r + i) * n + c + i);
                    if (i != 0) cells.push_back((r + i) * n + c - i);
                }
                sort(cells.begin(), cells.end());
                basis.add(move(cells), {k, r + 1, c + 1});
            }
        }
    }

    vector<Operation> answer;
    if (!basis.solve(move(target), answer)) {
        cout << -1 << '\n';
        return 0;
    }

    // 元の操作のうち、独立なものだけを各1回以下使うため、
    // 操作数は高々 N^2 <= 250000 で、出力上限を満たす。
    cout << answer.size() << '\n';
    for (const Operation& operation : answer) {
        cout << operation.k << ' ' << operation.r << ' ' << operation.c << '\n';
    }
}