結果
| 問題 | No.3602 Queen XOR Score |
| コンテスト | |
| ユーザー |
 tkdgkb
|
| 提出日時 | 2026-07-24 22:09:00 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,121 bytes |
| 記録 | |
| コンパイル時間 | 3,012 ms |
| コンパイル使用メモリ | 364,156 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-07-24 22:09:07 |
| 合計ジャッジ時間 | 6,237 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 WA * 2 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int h, w, q;
ll a[25][25];
vector<pair<int, int>> B;
inline bool is_adj(int r1, int c1, int r2, int c2) {
if (r1 == r2 && c1 == c2) return false;
if (r1 == r2 || c1 == c2) return true;
if (abs(r1 - r2) == abs(c1 - c2)) return true;
return false;
}
void solve() {
if (!(cin >> h >> w)) return;
int n = h * w;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < h; i++) {
if (i % 2 == 0) {
for (int j = 0; j < w; j++) B.push_back({i, j});
} else {
for (int j = w - 1; j >= 0; j--) B.push_back({i, j});
}
}
vector<ll> basis(60, 0);
vector<vector<int>> pivot_comb(60);
vector<vector<int>> nullspace;
for (int i = 0; i < n; i++) {
ll val = a[B[i].first][B[i].second];
vector<int> cur(n, 0);
cur[i] = 1;
for (int b = 59; b >= 0; b--) {
if ((val >> b) & 1) {
if (!basis[b]) {
basis[b] = val;
pivot_comb[b] = cur;
break;
}
val ^= basis[b];
for (int j = 0; j < n; j++) cur[j] ^= pivot_comb[b][j];
}
}
if (val == 0) {
nullspace.push_back(cur);
}
}
cin >> q;
mt19937 rng(1337);
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> c_base(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++) c_base[j] ^= pivot_comb[b][j];
}
}
if (rem != 0) {
cout << -1 << "\n";
continue;
}
int best_len = 1e9;
vector<pair<int, int>> best_path;
auto eval_y = [&](const vector<int>& c_arr) {
int sum_c = 0;
for (int v : c_arr) sum_c ^= v;
int extra = -1;
vector<int> mod_c = c_arr;
if (sum_c != (n % 2)) {
extra = n - 2;
mod_c[n - 2] ^= 1;
}
vector<int> y(n - 1);
y[0] = mod_c[0] ^ 1;
for (int i = 1; i < n - 1; i++) {
y[i] = mod_c[i] ^ 1 ^ y[i - 1];
}
int w_cnt = 0;
for (int v : y) w_cnt += v;
int limit = (extra == -1) ? (n / 2) : ((n - 1) / 2);
if (w_cnt <= limit) {
vector<pair<int, int>> path;
path.push_back(B[0]);
for (int i = 0; i < n - 1; i++) {
if (y[i] == 0) {
path.push_back(B[i + 1]);
} else {
path.push_back(B[i + 1]);
path.push_back(B[i]);
path.push_back(B[i + 1]);
}
}
if (extra != -1) path.push_back(B[extra]);
if ((int)path.size() - 1 < best_len) {
best_len = path.size() - 1;
best_path = path;
}
}
};
auto get_u = [&](int r, int v) {
return make_pair(B[r].first, B[v].second);
};
auto eval_star = [&](const vector<int>& c_arr) {
int ones = 0;
vector<int> c_list;
for (int i = 0; i < n; i++) {
if (c_arr[i]) {
ones++;
c_list.push_back(i);
}
}
if (ones == 0) {
vector<pair<int, int>> p = {B[0], B[1], B[0], B[1]};
if ((int)p.size() - 1 < best_len) {
best_len = p.size() - 1;
best_path = p;
}
return;
}
if (ones % 2 != 0) {
for (int r : c_list) {
vector<pair<int, int>> path = {B[r]};
for (int v : c_list) {
if (v == r) continue;
if (is_adj(B[r].first, B[r].second, B[v].first, B[v].second)) {
path.push_back(B[v]);
path.push_back(B[r]);
} else {
auto u = get_u(r, v);
path.push_back(u);
path.push_back(B[v]);
path.push_back(u);
path.push_back(B[r]);
}
}
if ((int)path.size() - 1 < best_len) {
best_len = path.size() - 1;
best_path = path;
}
}
} else {
for (int r : c_list) {
for (int e : c_list) {
if (r == e) continue;
vector<pair<int, int>> path = {B[r]};
for (int v : c_list) {
if (v == r || v == e) continue;
if (is_adj(B[r].first, B[r].second, B[v].first, B[v].second)) {
path.push_back(B[v]);
path.push_back(B[r]);
} else {
auto u = get_u(r, v);
path.push_back(u);
path.push_back(B[v]);
path.push_back(u);
path.push_back(B[r]);
}
}
if (is_adj(B[r].first, B[r].second, B[e].first, B[e].second)) {
path.push_back(B[e]);
} else {
auto u = get_u(r, e);
path.push_back(u);
path.push_back(B[e]);
path.push_back(u);
}
if ((int)path.size() - 1 < best_len) {
best_len = path.size() - 1;
best_path = path;
}
}
}
}
};
vector<int> c_cur = c_base;
eval_y(c_cur);
for (int iter = 0; iter < 2500; iter++) {
if (best_len <= 2 * n - 1) break;
c_cur = c_base;
for (auto& nv : nullspace) {
if (rng() % 2) {
for (int i = 0; i < n; i++) c_cur[i] ^= nv[i];
}
}
eval_y(c_cur);
}
if (best_len > 2 * n - 1) {
int max_iters = min(2500, 10000000 / (n * n * n + 1));
if (max_iters == 0) max_iters = 1;
c_cur = c_base;
eval_star(c_cur);
for (int iter = 0; iter < max_iters; iter++) {
if (best_len <= 2 * n - 1) break;
c_cur = c_base;
for (auto& nv : nullspace) {
if (rng() % 2) {
for (int i = 0; i < n; i++) c_cur[i] ^= nv[i];
}
}
eval_star(c_cur);
}
}
if (best_len > 2 * n - 1) {
cout << -1 << "\n";
} else {
cout << best_len << "\n";
for (auto& p : best_path) {
cout << p.first + 1 << " " << p.second + 1 << "\n";
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}