結果
| 問題 | No.3736 Purely Bool Hell |
| コンテスト | |
| ユーザー |
 aPNJ777
|
| 提出日時 | 2026-09-19 17:05:55 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 13,545 bytes |
| 記録 | |
| コンパイル時間 | 3,647 ms |
| コンパイル使用メモリ | 367,672 KB |
| 実行使用メモリ | 9,928 KB |
| 最終ジャッジ日時 | 2026-09-19 17:06:08 |
| 合計ジャッジ時間 | 12,339 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 30 WA * 9 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//using ll = long long;
using ld = long double;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
#define vv(type, name, h, w) vector<vector<type>> name(h, vector<type>(w))
#define vvv(type, name, h, w, l) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(l)))
#define vvvv(type, name, a, b, c, d) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(d))))
#define vvvvv(type, name, a, b, c, d, e) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(e)))))
#define elif else if
#define FOR1(a) for (long long _ = 0; _ < (long long)(a); _++)
#define FOR2(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR3(i, l, r) for (long long i = l; i < (long long)(r); i++)
#define FOR4(i, l, r, c) for (long long i = l; i < (long long)(r); i += c)
#define FOR1_R(a) for (long long _ = (long long)(a) - 1; _ >= 0; _--)
#define FOR2_R(i, n) for (long long i = (long long)(n) - 1; i >= (long long)(0); i--)
#define FOR3_R(i, l, r) for (long long i = (long long)(r) - 1; i >= (long long)(l); i--)
#define FOR4_R(i, l, r, c) for (long long i = (long long)(r) - 1; i >= (long long)(l); i -= (c))
#define overload4(a, b, c, d, e, ...) e
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_in(a, A) for (auto a: A)
#define FOR_each(a, A) for (auto &&a: A)
#define FOR_subset(t, s) for(long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) int(x.size())
int popcount(int x) { return __builtin_popcount(x); }
int popcount(uint32_t x) { return __builtin_popcount(x); }
int popcount(long long x) { return __builtin_popcountll(x); }
int popcount(uint64_t x) { return __builtin_popcountll(x); }
// __builtin_clz(x)は最上位bitからいくつ0があるか.
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(uint32_t x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(uint64_t x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// 入力
void rd() {}
void rd(char &c) { cin >> c; }
void rd(string &s) { cin >> s; }
void rd(int &x) { cin >> x; }
void rd(uint32_t &x) { cin >> x; }
void rd(long long &x) { cin >> x; }
void rd(uint64_t &x) { cin >> x; }
template<class T>
void rd(vector<T> &v) {
for (auto& x:v) rd(x);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define STRING(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
uint32_t __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
uint64_t __VA_ARGS__; \
read(__VA_ARGS__)
#define VC(t, a, n) \
vector<t> a(n); \
read(a)
#define VVC(t, a, h, w) \
vector<vector<t>> a(h, vector<t>(w)); \
read(a)
//出力
void wt() {}
void wt(const char c) { cout << c; }
void wt(const string s) { cout << s; }
void wt(int x) { cout << x; }
void wt(uint32_t x) { cout << x; }
void wt(long long x) { cout << x; }
void wt(uint64_t x) { cout << x; }
void wt(double x) { cout << fixed << setprecision(16) << x; }
void wt(long double x) { cout << fixed << setprecision(16) << x; }
template<class T>
void wt(const vector<T> v) {
int n = v.size();
for (int i = 0; i < n; i++) {
if (i) wt(' ');
wt(v[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
/////////////////////////////////////////////////////////////////////////////////////////
template <class T>
int bisect_left(const vector<T> &A, T x) {
auto idx = lower_bound(A.begin(), A.end(), x) - A.begin();
return idx;
}
template <class T>
int bisect_right(const vector<T> &A, T x) {
auto idx = upper_bound(A.begin(), A.end(), x) - A.begin();
return idx;
}
template <class T>
T min(vector<T> A) {
assert (A.size());
T S = A[0];
for (T a : A) S = min(a, S);
return S;
}
template <class T>
T max(vector<T> A) {
assert (A.size());
T S = A[0];
for (T a : A) S = max(a, S);
return S;
}
template <class T>
T add(T x, T y) { return x + y; }
template <class T>
bool chmin(T & x, T a) { return a < x ? (x = a, true) : false; }
template <class T>
bool chmax(T & x, T a) { return a > x ? (x = a, true) : false; }
template <class T>
T sum(vector<T> A) {
T S = 0;
for (int i = 0; i < int(A.size()); i++) S += A[i];
return S;
}
uint64_t random_u64(uint64_t l, uint64_t r) {
static std::random_device rd;
static std::mt19937_64 gen(rd());
std::uniform_int_distribution<uint64_t> dist(l, r);
return dist(gen);
}
long long gcd(long long a, long long b) {
while (a) {
b %= a;
if (b == 0) return a;
a %= b;
}
return b;
}
long long lcm(long long a, long long b) {
if (a * b == 0) return 0;
return a * b / gcd(a, b);
}
long long pow_mod(long long a, long long r, long long mod) {
long long res = 1, p = a % mod;
while (r) {
if ((r % 2) == 1) res = res * p % mod;
p = p * p % mod, r >>= 1;
}
return res;
}
long long mod_inv(long long a, long long mod) {
if (mod == 1) return 0;
a %= mod;
long long b = mod, s = 1, t = 0;
while (1) {
if (a == 1) return s;
t -= (b / a) * s;
b %= a;
if (b == 1) return t + mod;
s -= (a / b) * t;
a %= b;
}
}
long long Garner(vector<long long> Rem, vector<long long> Mod, int MOD) {
assert (Rem.size() == Mod.size());
long long mod = MOD;
Rem.push_back(0);
Mod.push_back(mod);
long long n = Mod.size();
vector<long long> coffs(n, 1);
vector<long long> constants(n, 0);
for (int i = 0; i < n - 1; i++) {
long long v = (Mod[i] + Rem[i] - constants[i]) % Mod[i];
v *= mod_inv(coffs[i], Mod[i]);
v %= Mod[i];
for (int j = i + 1; j < n; j++) {
constants[j] = (constants[j] + coffs[j] * v) % Mod[j];
coffs[j] = (coffs[j] * Mod[i]) % Mod[j];
}
}
return constants[n - 1];
}
long long Tonelli_Shanks(long long a, long long mod) {
a %= mod;
if (a < 2) return a;
if (pow_mod(a, (mod - 1) / 2, mod) != 1) return -1;
if (mod % 4 == 3) return pow_mod(a, (mod + 1) / 4, mod);
long long b = 3;
if (mod != 998244353) {
while (pow_mod(b, (mod - 1) / 2, mod) == 1) {
b = random_u64(2, mod - 1);
}
}
long long q = mod - 1;
long long Q = 0;
while (q % 2 == 0) {
Q++, q /= 2;
}
long long x = pow_mod(a, (q + 1) / 2, mod);
b = pow_mod(b, q, mod);
long long shift = 2;
while ((x * x) % mod != a) {
long long error = (((pow_mod(a, mod - 2, mod) * x) % mod) * x) % mod;
if (pow_mod(error, 1 << (Q - shift), mod) != 1) {
x = (x * b) % mod;
}
b = (b * b) % mod;
shift++;
}
return x;
}
long long floor_div(long long a, long long b) {
if (b < 0) a *= -1, b *= -1;
if (a >= 0) return a / b;
return -((-a + b - 1) / b);
}
long long ceil_div(long long a, long long b) {
if (b < 0) a *= -1, b *= -1;
if (a >= 0) return (a + b - 1) / b;
return - ((-a) / b);
}
/////////////////////////////////////////////////////////////////////////////////////////
/*
検索するとき
https://www.google.com/search?udm=14&q=
-ai
*/
/*
0, 1
all 1 の行, all 0 の列じゃないとダメなやつ分かる.
両方あったら無理
また all 1 でない行は 0 を含む.
どっちもない場合は xor の条件からつくれる
2 以上ならできる.
? ? 1 ... 1 0
0 ........... 0
...............
0............ 1
1 1 ..... 1 ? ?
all 1 の行がある.
列の条件は考えなくていい
all 1 の行 N - 1 以上. 残りも決定.
N - 2 個
1, N 行目のみ違う場合. 右上, 左下以外決定. 自由度 1
それいがい自由度 2
N - 3 個以下
自由度が決まっていない行分あるのでできる.
どっちもない場合おかしい
n >= 4 はできる.
? 1...1 0
? ?.... 0
0 ?...? ?
..
0 ? ....1
1 0 ....?
3 以下は全探索
*/
map<vector<int>, vector<vector<int>>> mp;
vector<vector<int>> calc(int N, vector<int> X, vector<int> Y, vector<int> Z) {
if (max(X) == 1 && min(Y) == 0) return {{-1}}; // 無理
if (max(X) == 0 && min(Y) == 1) {
if (N <= 3) {
if (mp.find(Z) != mp.end()) return mp[Z];
for (int bit = 0; bit < (1 << (N * N)); bit++) {
vector<vector<int>> res(N, vector<int>(N));
for (int i = 0; i < N * N; i++) {
int h = i / N, w = i % N;
res[h][w] = (bit >> i) & 1;
}
vector<int> x(N, 1), y(N), z(2 * N - 1);
FOR(i, N) FOR(j, N) {
x[i] &= res[i][j];
y[j] |= res[i][j];
z[i + j] ^= res[i][j];
}
if (x == X && y == Y && z == Z) {
mp[Z] = res;
return res;
}
}
mp[Z] = {{-1}};
return {{-1}};
}
vector<vector<int>> res(N, vector<int>(N)), seen(N, vector<int>(N));
for (int i = 1; i < N - 1; i++) res[0][i] = 1, Z[i] ^= 1, seen[0][i] = 1;
seen[0][N - 1] = 1, seen[1][N - 1] = 1;
for (int i = 2; i < N - 1; i++) seen[i][0] = 1;
res[N - 1][0] = 1, Z[N - 1] ^= 1, seen[N - 1][0] = 1;
res[N - 2][N - 1] = 1, Z[2 * N - 3] ^= 1, seen[N - 2][N - 1] = 1;
seen[N - 1][1] = 1;
FOR(i, N) FOR(j, N) {
if (seen[i][j]) continue;
res[i][j] = Z[i + j], Z[i + j] = 0;
}
return res;
}
if (max(X) == 1) {
vector<int> I;
vector<vector<int>> res(N, vector<int>(N));
vector<vector<int>> seen(N, vector<int>(N));
FOR(i, N) {
if (X[i] == 0) I.push_back(i);
else {
FOR(j, N) res[i][j] = 1, Z[i + j] ^= 1, seen[i][j] = 1;
}
}
if (len(I) == 0) {
if (max(Z) == 1) return {{-1}};
return res;
}
if (len(I) == 1) {
int i = I[0];
FOR(j, N) res[i][j] = Z[i + j], Z[i + j] = 0;
if (max(Z) == 1) return {{-1}};
if (min(res[i]) == 1) return {{-1}};
return res;
}
if (len(I) == 2 && I[0] == 0 && I[1] == N - 1) {
res[0][N - 1] = 1, res[N - 1][0] = 1;
for (int i = 0; i < N - 1; i++) res[0][i] = Z[i];
for (int i = 1; i < N; i++) res[N - 1][i] = Z[N - 1 + i];
if (X[N - 1] == 0) {
res[0][N - 1] = 0, res[N - 1][0] = 0;
return res;
}
if (max(min(res[0]), min(res[N - 1])) == 1) return {{-1}};
if (min(res[0]) == 1) res[0][N - 1] = 0;
else res[N - 1][0] = 0;
return res;
}
else {
seen[I[0]][N - 1] = 1;
FOR(i, 1, len(I)) seen[I[i]][0] = 1;
FOR(i, N) FOR(j, N) {
if (seen[i][j]) continue;
res[i][j] = Z[i + j], Z[i + j] = 0;
}
if (max(Z) == 1) return {{-1}};
return res;
}
}
else {
vector<int> I;
vector<vector<int>> res(N, vector<int>(N, 1));
vector<vector<int>> seen(N, vector<int>(N));
FOR(i, N) FOR(j, N) Z[i + j] ^= 1;
FOR(i, N) {
if (Y[i] == 1) I.push_back(i);
else {
FOR(j, N) res[j][i] = 0, Z[i + j] ^= 1, seen[j][i] = 1;
}
}
if (len(I) == 0) {
if (max(Z) == 1) return {{-1}};
return res;
}
if (len(I) == 1) {
int i = I[0];
int s = 0;
FOR(j, N) res[j][i] ^= Z[i + j], Z[i + j] = 0, s += res[j][i];
if (max(Z) == 1) return {{-1}};
if (s == 0) return {{-1}};
return res;
}
if (len(I) == 2 && I[0] == 0 && I[1] == N - 1) {
res[N - 1][0] = 0, res[0][N - 1] = 0;
for (int i = 0; i < N - 1; i++) res[i][0] = Z[i];
for (int i = 1; i < N; i++) res[i][N - 1] = Z[N - 1 + i];
if (X[N - 1] == 0) {
res[N - 1][0] = 1, res[0][N - 1] = 1;
return res;
}
int s = 0, t = 0;
FOR(i, N) s += res[i][0], t += res[i][N - 1];
if (max(s, t) == 0) return {{-1}};
if (s == 0) res[N - 1][0] = 1;
else res[0][N - 1] = 1;
return res;
}
else {
seen[N - 1][I[0]] = 1;
FOR(i, 1, len(I)) seen[0][I[i]] = 1;
FOR(i, N) FOR(j, N) {
if (seen[i][j]) continue;
res[i][j] ^= Z[i + j], Z[i + j] = 0;
}
if (max(Z) == 1) return {{-1}};
return res;
}
}
return {{-1}};
}
void solve() {
INT(N);
VC(int, X, N);
VC(int, Y, N);
VC(int, Z, 2 * N - 1);
if (N == 1) {
if (X[0] == Y[0] && X[0] == Z[0]) return print(X[0]);
return print(-1);
}
vector<vector<int>> ans(N, vector<int>(N));
for (int d = 0; d < 30; d++) {
vector<int> x, y, z;
for (int i = 0; i < N; i++) x.push_back((X[i] >> d) & 1), y.push_back((Y[i] >> d) & 1);
for (int i = 0; i < 2 * N - 1; i++) z.push_back((Z[i] >> d) & 1);
auto res = calc(N, x, y, z);
if (res[0][0] == -1) return print(-1);
FOR(i, N) FOR(j, N) ans[i][j] |= res[i][j] << d;
}
FOR_in(res, ans) print(res);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testcases = 1;
cin >> testcases;
FOR(testcases) solve();
}