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

• 問題: No.3602 Queen XOR Score
• ユーザー: tkdgkb
• 提出日時: 2026-07-24 21:49:07
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 5,412 bytes
• コンパイル時間: 2,469 ms
• コンパイル使用メモリ: 358,796 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-24 21:51:04
• 合計ジャッジ時間: 4,507 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 19 WA * 10

ソースコード

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

using ll = long long;

int h, w, q;
ll a[25][25];

inline bool is_adj(int x1, int y1, int x2, int y2) {
    if (x1 == x2 && y1 == y2) return false;
    if (x1 == x2 || y1 == y2) return true;
    if (abs(x1 - x2) == abs(y1 - y2)) return true;
    return false;
}

void solve() {
    cin >> h >> w; 
    int n = h * w;
    vector<pair<int, int>> cells;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
            cells.push_back({i, j});
        }
    }

    vector<ll> basis(60, 0);
    vector<vector<int>> pivot_comb(60);
    vector<int> pivot_col;

    for (int i = 0; i < n; i++) {
        ll val = a[cells[i].first][cells[i].second];
        vector<int> cur_comb(n, 0);
        cur_comb[i] = 1;

        for (int b = 59; b >= 0; b--) {
            if ((val >> b) & 1) {
                if (!basis[b]) {
                    basis[b] = val;
                    pivot_comb[b] = cur_comb;
                    pivot_col.push_back(b);
                    break;
                }
                val ^= basis[b];
                for (int j = 0; j < n; j++) {
                    cur_comb[j] ^= pivot_comb[b][j];
                }
            }
        }
    }

    vector<vector<int>> nullspace;
    for (int i = 0; i < n; i++) {
        ll val = a[cells[i].first][cells[i].second];
        vector<int> cur_comb(n, 0);
        cur_comb[i] = 1;

        for (int b = 59; b >= 0; b--) {
            if ((val >> b) & 1) {
                if (basis[b]) {
                    val ^= basis[b];
                    for (int j = 0; j < n; j++) {
                        cur_comb[j] ^= pivot_comb[b][j];
                    }
                }
            }
        }
        if (val == 0) {
            int cnt = 0;
            for (int x : cur_comb) cnt += x;
            if (cnt > 0) nullspace.push_back(cur_comb);
        }
    }

    cin >> q;
    while (q--) {
        ll x;
        cin >> x;

        if (x == 0) {
            cout << 3 << "\n";
            cout << 1 << " " << 1 << "\n";
            cout << 1 << " " << 2 << "\n";
            cout << 1 << " " << 1 << "\n";
            cout << 1 << " " << 2 << "\n";
            continue;
        }

        ll rem = x;
        vector<int> sol(n, 0);
        for (int b = 59; b >= 0; b--) {
            if ((rem >> b) & 1) {
                if (!basis[b]) {
                    rem = -1;
                    break;
                }
                rem ^= basis[b];
                for (int j = 0; j < n; j++) {
                    sol[j] ^= pivot_comb[b][j];
                }
            }
        }

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

        int sol_cnt = 0;
        for (int v : sol) sol_cnt += v;

        if (sol_cnt % 2 == 0) {
            for (auto &null_v : nullspace) {
                int null_cnt = 0;
                for (int v : null_v) null_cnt += v;
                if (null_cnt % 2 != 0) {
                    for (int j = 0; j < n; j++) {
                        sol[j] ^= null_v[j];
                    }
                    sol_cnt = 0;
                    for (int v : sol) sol_cnt += v;
                    break;
                }
            }
        }

        vector<int> c_indices;
        for (int i = 0; i < n; i++) {
            if (sol[i]) c_indices.push_back(i);
        }

        vector<pair<int, int>> path;

        if (sol_cnt % 2 != 0) {
            int r_idx = c_indices[0];
            auto r = cells[r_idx];
            path.push_back(r);

            for (size_t i = 1; i < c_indices.size(); i++) {
                auto v = cells[c_indices[i]];
                if (is_adj(r.first, r.second, v.first, v.second)) {
                    path.push_back(v);
                    path.push_back(r);
                } else {
                    auto u = make_pair(r.first, v.second);
                    path.push_back(u);
                    path.push_back(v);
                    path.push_back(u);
                    path.push_back(r);
                }
            }
        } else {
            int r_idx = c_indices[0];
            int w_idx = c_indices[1];
            auto r = cells[r_idx];
            auto w = cells[w_idx];

            path.push_back(r);

            for (size_t i = 2; i < c_indices.size(); i++) {
                auto v = cells[c_indices[i]];
                if (is_adj(r.first, r.second, v.first, v.second)) {
                    path.push_back(v);
                    path.push_back(r);
                } else {
                    auto u = make_pair(r.first, v.second);
                    path.push_back(u);
                    path.push_back(v);
                    path.push_back(u);
                    path.push_back(r);
                }
            }

            if (is_adj(r.first, r.second, w.first, w.second)) {
                path.push_back(w);
            } else {
                auto u = make_pair(r.first, w.second);
                path.push_back(u);
                path.push_back(r);
                path.push_back(u);
                path.push_back(w);
            }
        }

        cout << path.size() - 1 << "\n";
        for (auto &p : path) {
            cout << p.first << " " << p.second << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}