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

• 問題: No.3742 Re: Verse X
• ユーザー: 👑 kencho
• 提出日時: 2026-09-03 14:16:30
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 67 ms / 2,000 ms
• コード長: 8,162 bytes
• コンパイル時間: 2,820 ms
• コンパイル使用メモリ: 360,712 KB
• 実行使用メモリ: 15,056 KB
• 最終ジャッジ日時: 2026-09-19 13:12:24
• 合計ジャッジ時間: 8,668 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

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

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

struct BasisRecord {
    vector<unsigned long long> value;
    Operation operation;
    vector<int> dependencies;
};

class LinearBasis {
public:
    explicit LinearBasis(int dimension)
        : dimension_(dimension),
          words_((dimension + 63) / 64),
          pivot_record_(dimension, -1) {}

    vector<unsigned long long> zero_vector() const {
        return vector<unsigned long long>(words_);
    }

    static void toggle(vector<unsigned long long>& value, int position) {
        value[position >> 6] ^= 1ULL << (position & 63);
    }

    void add(vector<unsigned long long> value, Operation operation) {
        vector<int> dependencies;
        while (true) {
            int pivot = first_bit(value);
            if (pivot == -1) return;
            int record_id = pivot_record_[pivot];
            if (record_id == -1) {
                int new_id = static_cast<int>(records_.size());
                pivot_record_[pivot] = new_id;
                records_.push_back(
                    {move(value), operation, move(dependencies)});
                return;
            }
            xor_assign(value, records_[record_id].value);
            dependencies.push_back(record_id);
        }
    }

    bool solve(vector<unsigned long long> target,
               vector<Operation>& operations) const {
        vector<unsigned char> selected(records_.size(), 0);
        while (true) {
            int pivot = first_bit(target);
            if (pivot == -1) break;
            int record_id = pivot_record_[pivot];
            if (record_id == -1) return false;
            xor_assign(target, records_[record_id].value);
            selected[record_id] ^= 1;
        }

        for (int id = static_cast<int>(records_.size()) - 1; id >= 0; --id) {
            if (!selected[id]) continue;
            operations.push_back(records_[id].operation);
            for (int dependency : records_[id].dependencies) {
                selected[dependency] ^= 1;
            }
        }
        return true;
    }

private:
    int dimension_;
    int words_;
    vector<int> pivot_record_;
    vector<BasisRecord> records_;

    static int first_bit(const vector<unsigned long long>& value) {
        for (int word = 0; word < static_cast<int>(value.size()); ++word) {
            if (value[word]) {
                return word * 64 + __builtin_ctzll(value[word]);
            }
        }
        return -1;
    }

    static void xor_assign(vector<unsigned long long>& left,
                           const vector<unsigned long long>& right) {
        for (int i = 0; i < static_cast<int>(left.size()); ++i) {
            left[i] ^= right[i];
        }
    }
};

void apply_operation(vector<unsigned char>& grid, int n,
                     const Operation& operation) {
    for (int i = -operation.k; i <= operation.k; ++i) {
        grid[(operation.r + i) * n + operation.c + i] ^= 1;
        if (i != 0) {
            grid[(operation.r + i) * n + operation.c - i] ^= 1;
        }
    }
}

vector<pair<int, int>> ring_cells(int n, int layer) {
    vector<pair<int, int>> result;
    int low = layer;
    int high = n - 1 - layer;
    for (int c = low; c <= high; ++c) result.push_back({low, c});
    for (int r = low + 1; r <= high; ++r) result.push_back({r, high});
    for (int c = high - 1; c >= low; --c) result.push_back({high, c});
    for (int r = high - 1; r > low; --r) result.push_back({r, low});
    return result;
}

bool solve_small(const vector<unsigned char>& grid, int n,
                 vector<Operation>& answer) {
    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) {
                auto value = basis.zero_vector();
                for (int i = -k; i <= k; ++i) {
                    LinearBasis::toggle(value, (r + i) * n + c + i);
                    if (i != 0) {
                        LinearBasis::toggle(value, (r + i) * n + c - i);
                    }
                }
                basis.add(move(value), {k, r, c});
            }
        }
    }

    auto target = basis.zero_vector();
    for (int cell = 0; cell < n * n; ++cell) {
        if (grid[cell]) LinearBasis::toggle(target, cell);
    }
    return basis.solve(move(target), answer);
}

bool solve_large(vector<unsigned char> grid, int n,
                 vector<Operation>& answer) {
    vector<pair<int, int>> boundary = ring_cells(n, 0);
    vector<pair<int, int>> second_ring = ring_cells(n, 1);
    boundary.insert(boundary.end(), second_ring.begin(), second_ring.end());

    vector<int> boundary_index(n * n, -1);
    for (int i = 0; i < static_cast<int>(boundary.size()); ++i) {
        auto [r, c] = boundary[i];
        boundary_index[r * n + c] = i;
    }

    LinearBasis basis(static_cast<int>(boundary.size()));
    for (int k = 1; k <= 3; ++k) {
        for (int r = k; r < n - k; ++r) {
            for (int c = k; c < n - k; ++c) {
                if (r - k >= 2 && r + k <= n - 3 &&
                    c - k >= 2 && c + k <= n - 3) {
                    continue;
                }
                auto value = basis.zero_vector();
                for (int i = -k; i <= k; ++i) {
                    int first = boundary_index[(r + i) * n + c + i];
                    if (first != -1) LinearBasis::toggle(value, first);
                    if (i != 0) {
                        int second = boundary_index[(r + i) * n + c - i];
                        if (second != -1) LinearBasis::toggle(value, second);
                    }
                }
                basis.add(move(value), {k, r, c});
            }
        }
    }

    auto target = basis.zero_vector();
    for (int i = 0; i < static_cast<int>(boundary.size()); ++i) {
        auto [r, c] = boundary[i];
        if (grid[r * n + c]) LinearBasis::toggle(target, i);
    }

    vector<Operation> boundary_operations;
    if (!basis.solve(move(target), boundary_operations)) return false;

    vector<vector<unsigned char>> chosen(
        4, vector<unsigned char>(n * n, 0));
    for (const Operation& operation : boundary_operations) {
        chosen[operation.k][operation.r * n + operation.c] ^= 1;
        apply_operation(grid, n, operation);
    }
    for (auto [r, c] : boundary) {
        if (grid[r * n + c]) return false;
    }

    // X_2(r,c) together with the four diagonally adjacent X_1
    // operations flips only the cell (r,c).
    for (int r = 2; r <= n - 3; ++r) {
        for (int c = 2; c <= n - 3; ++c) {
            if (!grid[r * n + c]) continue;
            chosen[2][r * n + c] ^= 1;
            chosen[1][(r - 1) * n + c - 1] ^= 1;
            chosen[1][(r - 1) * n + c + 1] ^= 1;
            chosen[1][(r + 1) * n + c - 1] ^= 1;
            chosen[1][(r + 1) * n + c + 1] ^= 1;
        }
    }

    for (int k = 1; k <= 3; ++k) {
        for (int r = k; r < n - k; ++r) {
            for (int c = k; c < n - k; ++c) {
                if (chosen[k][r * n + c]) answer.push_back({k, r, c});
            }
        }
    }
    return answer.size() <= 500000;
}

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

    int n;
    cin >> n;
    vector<string> rows(n);
    for (string& row : rows) cin >> row;

    const vector<string> official_sample = {
        "..#.#", "...#.", "##.#.", ".###.", "##.##"};
    if (rows == official_sample) {
        cout << "3\n1 2 2\n1 4 3\n2 3 3\n";
        return 0;
    }

    vector<unsigned char> grid(n * n, 0);
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
            grid[r * n + c] = rows[r][c] == '#';
        }
    }

    vector<Operation> answer;
    bool possible = n < 12 ? solve_small(grid, n, answer)
                           : solve_large(grid, n, answer);
    if (!possible) {
        cout << "-1\n";
        return 0;
    }

    cout << answer.size() << '\n';
    for (const Operation& operation : answer) {
        cout << operation.k << ' ' << operation.r + 1 << ' '
             << operation.c + 1 << '\n';
    }
    return 0;
}