#1173160 (C++23) No.3602 Queen XOR Score

• 問題: No.3602 Queen XOR Score
• ユーザー: tkdgkb
• 提出日時: 2026-07-24 22:20:08
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 21 ms / 2,000 ms
• コード長: 5,285 bytes
• コンパイル時間: 1,504 ms
• コンパイル使用メモリ: 202,912 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-24 22:22:31
• 合計ジャッジ時間: 3,648 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 29

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    int N = H * W;
    vector<unsigned long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<vector<int>> adj(N);
    int dr[] = {-1, 1, 0, 0, -1, -1, 1, 1};
    int dc[] = {0, 0, -1, 1, -1, 1, -1, 1};

    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            int u = r * W + c;
            for (int d = 0; d < 8; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                while (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                    int v = nr * W + nc;
                    adj[u].push_back(v);
                    nr += dr[d];
                    nc += dc[d];
                }
            }
        }
    }

    vector<unsigned long long> basis(60, 0);
    vector<bitset<400>> basis_mask(60);
    bitset<400> zero_mask;
    bool has_zero_mask = false;

    for (int i = 0; i < N; i++) {
        unsigned long long val = A[i];
        bitset<400> mask;
        mask.set(i);

        for (int b = 59; b >= 0; b--) {
            if ((val >> b) & 1ULL) {
                if (basis[b] == 0) {
                    basis[b] = val;
                    basis_mask[b] = mask;
                    break;
                } else {
                    val ^= basis[b];
                    mask ^= basis_mask[b];
                }
            }
        }

        if (val == 0 && mask.any() && !has_zero_mask) {
            zero_mask = mask;
            has_zero_mask = true;
        }
    }

    int Q;
    if (!(cin >> Q)) return 0;

    while (Q--) {
        unsigned long long X;
        cin >> X;

        unsigned long long cur_val = X;
        bitset<400> target_mask;
        bool possible = true;

        for (int b = 59; b >= 0; b--) {
            if ((cur_val >> b) & 1ULL) {
                if (basis[b] == 0) {
                    possible = false;
                    break;
                }
                cur_val ^= basis[b];
                target_mask ^= basis_mask[b];
            }
        }

        if (!possible || cur_val != 0) {
            cout << -1 << "\n";
            continue;
        }

        if (target_mask.none()) {
            if (has_zero_mask) {
                target_mask = zero_mask;
            } else {
                cout << -1 << "\n";
                continue;
            }
        }

        int root = -1;
        int extra_move = -1;

        if (target_mask.count() % 2 == 0) {
            for (int i = 0; i < N; i++) {
                if (target_mask.test(i)) {
                    root = i;
                    break;
                }
            }
            extra_move = adj[root][0];
            target_mask.flip(extra_move); 
        } else {
            for (int i = 0; i < N; i++) {
                if (target_mask.test(i)) {
                    root = i;
                    break;
                }
            }
        }

        vector<int> S;
        for (int i = 0; i < N; i++) {
            if (target_mask.test(i)) {
                S.push_back(i);
            }
        }

        vector<int> parent(N, -1);
        vector<vector<int>> children(N);
        vector<bool> vis(N, false);
        queue<int> q;
        vector<int> bfs_order;

        q.push(root);
        vis[root] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            bfs_order.push_back(u);

            for (int v : adj[u]) {
                if (!vis[v]) {
                    vis[v] = true;
                    parent[v] = u;
                    children[u].push_back(v);
                    q.push(v);
                }
            }
        }

        vector<bool> in_S(N, false);
        for (int v : S) in_S[v] = true;

        vector<bool> is_relevant(N, false);
        for (int i = (int)bfs_order.size() - 1; i >= 0; i--) {
            int u = bfs_order[i];
            if (in_S[u]) is_relevant[u] = true;
            for (int v : children[u]) {
                if (is_relevant[v]) is_relevant[u] = true;
            }
        }

        vector<int> path;
        vector<int> visit_count(N, 0);

        auto dfs = [&](auto& self, int u) -> void {
            path.push_back(u);
            visit_count[u]++;

            for (int v : children[u]) {
                if (!is_relevant[v]) continue;

                self(self, v);

                int target_parity = in_S[v] ? 1 : 0;
                if (visit_count[v] % 2 != target_parity) {
                    path.push_back(u); visit_count[u]++;
                    path.push_back(v); visit_count[v]++;
                    path.push_back(u); visit_count[u]++;
                } else {
                    path.push_back(u); visit_count[u]++;
                }
            }
        };

        dfs(dfs, root);

        if (extra_move != -1) {
            path.push_back(extra_move);
            visit_count[extra_move]++;
        }

        cout << path.size() - 1 << "\n";
        for (int u : path) {
            cout << (u / W) + 1 << " " << (u % W) + 1 << "\n";
        }
    }

    return 0;
}