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

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

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

ソースコード

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

int h, w, q;
ll a[25][25];
vector<pair<int, int>> cells;

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;
}

vector<pair<int, int>> get_petal(vector<pair<int, int>>& C_list) {
    if (C_list.empty()) return {};
    vector<pair<int, int>> best;
    for (auto r : C_list) {
        vector<pair<int, int>> path = {r};
        vector<pair<int, int>> adj, non_adj;
        for (auto v : C_list) {
            if (v == r) continue;
            if (is_adj(r.first, r.second, v.first, v.second)) adj.push_back(v);
            else non_adj.push_back(v);
        }

        bool need_half = (C_list.size() % 2 == 0);

        for (int i = 0; i < (int)non_adj.size(); i++) {
            auto v = non_adj[i];
            pair<int, int> u = {r.first, v.second};
            if (need_half && adj.empty() && i == (int)non_adj.size() - 1) {
                path.push_back(u); path.push_back(v); path.push_back(u);
            } else {
                path.push_back(u); path.push_back(v); path.push_back(u); path.push_back(r);
            }
        }
        for (int i = 0; i < (int)adj.size(); i++) {
            auto v = adj[i];
            if (need_half && i == (int)adj.size() - 1) {
                path.push_back(v);
            } else {
                path.push_back(v); path.push_back(r);
            }
        }

        if (best.empty() || path.size() < best.size()) best = path;
    }
    return best;
}

vector<pair<int, int>> get_ham(int C[25][25]) {
    vector<pair<int, int>> B;
    for (int i = 1; i <= h; i++) {
        if (i % 2 != 0) {
            for (int j = 1; j <= w; j++) B.push_back({i, j});
        } else {
            for (int j = w; j >= 1; j--) B.push_back({i, j});
        }
    }
    int sum_C = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) sum_C ^= C[i][j];
    }
    if (sum_C != (B.size() % 2)) B.push_back(B[B.size() - 2]);

    vector<pair<int, int>> path;
    path.push_back(B[0]);
    int counts[25][25] = {0};
    counts[B[0].first][B[0].second]++;

    map<pair<int, int>, int> last_idx;
    for (int i = 0; i < (int)B.size() - 1; i++) {
        last_idx[B[i]] = i;
    }

    for (int i = 0; i < (int)B.size() - 1; i++) {
        auto curr = B[i];
        auto nxt = B[i + 1];
        if (last_idx[curr] == i) {
            if (counts[curr.first][curr.second] % 2 != C[curr.first][curr.second]) {
                path.push_back(nxt);
                path.push_back(curr);
                counts[nxt.first][nxt.second]++;
                counts[curr.first][curr.second]++;
            }
        }
        path.push_back(nxt);
        counts[nxt.first][nxt.second]++;
    }
    return path;
}

void solve() {
    if (!(cin >> h >> w)) return;
    int n = h * w;
    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);

    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;
                    break;
                }
                val ^= basis[b];
                for (int j = 0; j < n; j++) cur_comb[j] ^= pivot_comb[b][j];
            }
        }
    }

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

        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 C[25][25] = {0};
        vector<pair<int, int>> C_list;
        for (int i = 0; i < n; i++) {
            if (sol[i]) {
                C[cells[i].first][cells[i].second] = 1;
                C_list.push_back(cells[i]);
            }
        }

        if (C_list.empty()) {
            cout << 3 << "\n";
            cout << 1 << " " << 1 << "\n";
            cout << 1 << " " << 2 << "\n";
            cout << 1 << " " << 1 << "\n";
            cout << 1 << " " << 2 << "\n";
            continue;
        }

        vector<pair<int, int>> p1 = get_petal(C_list);
        vector<pair<int, int>> p2 = get_ham(C);

        vector<pair<int, int>> best;
        if (!p1.empty() && !p2.empty()) {
            best = (p1.size() < p2.size()) ? p1 : p2;
        } else if (!p1.empty()) {
            best = p1;
        } else {
            best = p2;
        }

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

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