結果
| 問題 | No.3736 Purely Bool Hell |
| コンテスト | |
| ユーザー |
 yuma220284
|
| 提出日時 | 2026-09-19 17:57:20 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 17,205 bytes |
| 記録 | |
| コンパイル時間 | 4,840 ms |
| コンパイル使用メモリ | 406,164 KB |
| 実行使用メモリ | 9,928 KB |
| 最終ジャッジ日時 | 2026-09-19 17:57:44 |
| 合計ジャッジ時間 | 16,908 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 14 WA * 9 RE * 16 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
typedef pair<ll,ppl> pppl;
typedef pair<ll,pppl> pppppl;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
// #define F first
// #define S second
#define bs(A,x) binary_search(all(A),x)
#define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin())
#define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin())
#define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x))
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
//*
using mint=modint998244353;
const ll mod=998244353;
//*/
/*
using mint=modint1000000007;
const ll mod=1000000007;
//*/
//using mint=modint;
//*
typedef vector<mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
typedef vector<vvvm> vvvvm;
ostream&operator<<(ostream&os,mint a){os<<a.val();return os;}
istream&operator>>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;}
//*/
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
namespace Random {
mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count());
using u64 = unsigned long long;
u64 get() {
return randgen();
}
template <typename T> T get(T L) { // [0,L]
return get() % (L + 1);
}
template <typename T> T get(T L, T R) { // [L,R]
return get(R - L) + L;
}
}; // namespace Random
/**
* @brief Random
*/
bool Judge(int N, vector<int> X, vector<int> Y, vector<int> Z, vector<vector<int>> ANS) {
vector<int> A(N,(1<<30)-1), B(N,0), C(N,0);
rep(i,0,N) {
rep(j,0,N) {
A[i] &= ANS[i][j];
B[j] |= ANS[i][j];
C[i+j] ^= ANS[i][j];
}
}
return (X==A && Y==B && Z==C);
}
pair<bool,vector<vector<int>>> Calc(int N, vector<int> X, vector<int> Y, vector<int> Z) {
vector<vector<int>> ANS(N, vector<int>(N, -1));
int CX = 0, CY = 0;
rep(i,0,N) {
if (X[i] == 1) {
CX = true;
rep(j,0,N) ANS[i][j] = 1;
}
}
rep(i,0,N) {
if (Y[i] == 0) {
CY = true;
rep(j,0,N) {
if (ANS[j][i] == 1) {
return {false,ANS};
}
ANS[j][i] = 0;
}
}
}
assert(CX == 0 || CY == 0);
if (CX == 0 && CY > 0) {
vector<bool> B(N,false);
rep(i,0,N) if (Y[i] == 0) B[i] = true;
vector<int> C(N*2-1,0);
vector<vector<int>> G(N*2-1);
rep(i,0,N) {
rep(j,0,N) {
if (ANS[i][j] != -1) C[i+j] ^= ANS[i][j];
else G[i+j].push_back(j);
}
}
rep(i,0,N*2-1) {
bool check = false;
if ((C[i]^Z[i]) == sz(G[i])%2) check = true;
int ID = -1;
if (!check) {
rep(y,0,N) {
int x = i-y;
if (x < 0 || N <= x) continue;
if (ANS[x][y] == -1 && B[y]) ID = y;
}
}
if (check || ID != -1) {
rep(y,0,N) {
int x = i-y;
if (x < 0 || N <= x) continue;
if (ANS[x][y] != -1) continue;
if (y == ID) {
ANS[x][y] = 0;
C[i] ^= 0;
check = true;
}
else {
ANS[x][y] = 1;
C[i] ^= 1;
B[y] = true;
}
}
}
else {
rrep(y,0,N) {
int x = i-y;
if (x < 0 || N <= x) continue;
if (ANS[x][y] != -1) continue;
if (!check) {
ANS[x][y] = 0;
C[i] ^= 0;
check = true;
}
else {
ANS[x][y] = 1;
C[i] ^= 1;
B[y] = true;
}
}
}
}
rep(i,0,N) {
if (!B[i]) return {false,ANS};
}
return {true,ANS};
// vector<bool> B(N,false);
// rep(i,0,N) if (Y[i] == 1) B[i] = true;
// vector<int> C(N*2-1,0);
// vector<vector<int>> G(N*2-1);
// vector<vector<int>> H(N);
// queue<int> Q;
// rep(i,0,N) {
// rep(j,0,N) {
// if (ANS[i][j] == -1) {
// G[i+j].push_back(j);
// H[j].push_back(i+j);
// }
// else {
// C[i+j] ^= ANS[i][j];
// }
// }
// }
// rep(i,0,N*2-1) {
// if (G[i].empty() && C[i] != Z[i]) {
// return {false,ANS};
// }
// if ((C[i]^Z[i]) == (sz(G[i])%2)) {
// for (int y : G[i]) {
// int x = i-y;
// ANS[x][y] = 1;
// C[i] ^= 1;
// B[y] = true;
// Q.push(y);
// }
// G[i].clear();
// }
// }
// rep(i,0,N*2-1) {
// if ((C[i]^Z[i]) == (sz(G[i])%2)) {
// int id = -1;
// for (int y : G[i]) {
// if (B[y]) {
// id = y;
// break;
// }
// }
// if (id != -1) {
// ANS[i-id][id] = 0;
// C[i] ^= 0;
// for (int x : G[i]) {
// if (x == id) continue;
// int y = i-x;
// assert(ANS[x][y] == -1);
// ANS[x][y] = 1;
// C[i] ^= 1;
// if (!B[y]) {
// B[y] = true;
// Q.push(y);
// }
// }
// G[i].clear();
// }
// }
// }
// while(!Q.empty()) {
// int y = Q.front();
// Q.pop();
// for (int z : H[y]) {
// if ((C[z]^Z[z]) != (sz(G[z])%2)) {
// int x = z-y;
// ANS[x][y] = 0;
// C[z] ^= 0;
// for (int ny : G[z]) {
// if (ny == y) continue;
// int nx = z-ny;
// assert(ANS[nx][ny] == -1);
// ANS[nx][ny] = 1;
// C[z] ^= 1;
// if (!B[ny]) {
// B[ny] = true;
// Q.push(ny);
// }
// }
// G[z].clear();
// }
// }
// }
// rep(i,0,N*2-1) G[i].clear();
// rep(i,0,N) H[i].clear();
// rep(i,0,N) {
// rep(j,0,N) {
// if (ANS[i][j] == -1) {
// G[i+j].push_back(j);
// H[j].push_back(i+j);
// }
// }
// }
}
//---------------------------------------------
if (CY == 0 && CX > 0) {
vector<bool> A(N,false);
rep(i,0,N) if (X[i] == 1) A[i] = true;
vector<int> C(N*2-1,0);
vector<vector<int>> G(N*2-1);
rep(i,0,N) {
rep(j,0,N) {
if (ANS[i][j] != -1) C[i+j] ^= ANS[i][j];
else G[i+j].push_back(i);
}
}
rep(i,0,N*2-1) {
bool check = false;
if ((C[i]^Z[i]) == 0) check = true;
int ID = -1;
if (!check) {
rep(x,0,N) {
int y = i-x;
if (y < 0 || N <= y) continue;
if (ANS[x][y] == -1 && A[x]) ID = x;
}
}
if (check || ID != -1) {
rep(x,0,N) {
int y = i-x;
if (y < 0 || N <= y) continue;
if (ANS[x][y] != -1) continue;
if (x == ID) {
ANS[x][y] = 1;
C[i] ^= 1;
check = true;
}
else {
ANS[x][y] = 0;
C[i] ^= 0;
A[x] = true;
}
}
}
else {
rrep(x,0,N) {
int y = i-x;
if (y < 0 || N <= y) continue;
if (ANS[x][y] != -1) continue;
if (!check) {
ANS[x][y] = 1;
C[i] ^= 1;
check = true;
}
else {
ANS[x][y] = 0;
C[i] ^= 0;
A[x] = true;
}
}
}
}
rep(i,0,N) {
if (!A[i]) return {false,ANS};
}
return {true,ANS};
// vector<bool> A(N,false);
// rep(i,0,N) if (X[i] == 1) A[i] = true;
// vector<int> C(N*2-1,0);
// vector<vector<int>> G(N*2-1);
// vector<vector<int>> H(N);
// queue<int> Q;
// rep(i,0,N) {
// rep(j,0,N) {
// if (ANS[i][j] == -1) {
// G[i+j].push_back(i);
// H[i].push_back(i+j);
// }
// else {
// C[i+j] ^= ANS[i][j];
// }
// }
// }
// rep(i,0,N*2-1) {
// if (G[i].empty() && C[i] != Z[i]) {
// return {false,ANS};
// }
// if ((C[i]^Z[i]) == 0) {
// for (int x : G[i]) {
// int y = i-x;
// ANS[x][y] = 0;
// C[i] ^= 0;
// A[x] = true;
// }
// G[i].clear();
// }
// }
// rep(i,0,N*2-1) {
// if ((C[i]^Z[i]) == 1) {
// int id = -1;
// for (int x : G[i]) {
// if (A[x]) {
// id = x;
// break;
// }
// }
// if (id != -1) {
// ANS[id][i-id] = 1;
// C[i] ^= 1;
// for (int x : G[i]) {
// if (x == id) continue;
// int y = i-x;
// assert(ANS[x][y] == -1);
// ANS[x][y] = 0;
// C[i] ^= 0;
// if (!A[x]) {
// A[x] = true;
// Q.push(x);
// }
// }
// G[i].clear();
// }
// }
// }
// while(!Q.empty()) {
// int x = Q.front();
// Q.pop();
// for (int z : H[x]) {
// if ((C[z]^Z[z]) != 0) {
// int y = z-x;
// ANS[x][y] = 1;
// C[z] ^= 1;
// for (int nx : G[z]) {
// if (nx == x) continue;
// int ny = z-nx;
// assert(ANS[nx][ny] == -1);
// ANS[nx][ny] = 0;
// C[z] ^= 0;
// if (!A[nx]) {
// A[nx] = true;
// Q.push(nx);
// }
// }
// G[z].clear();
// }
// }
// }
// rep(i,0,N*2-1) G[i].clear();
// rep(i,0,N) H[i].clear();
// rep(i,0,N) {
// rep(j,0,N) {
// if (ANS[i][j] == -1) {
// G[i+j].push_back(i);
// H[i].push_back(i+j);
// }
// }
// }
}
//----------------------------------------------------------
if (CX == 0 && CY == 0) {
if (N <= 3) {
rep(i,0,1<<(N*N)) {
rep(j,0,N*N) {
int x = j/N, y = j%N;
if (i & (1<<j)) ANS[x][y] = 0;
else ANS[x][y] = 1;
}
vector<int> A(N,1), B(N,0), C(N*2-1,0);
rep(i,0,N) {
rep(j,0,N) {
A[i] &= ANS[i][j];
B[j] |= ANS[i][j];
C[i+j] ^= ANS[i][j];
}
}
if (A==X && B==Y && C==Z) {
return {true,ANS};
}
}
return {false,ANS};
}
assert(N >= 4);
if (Z[0] == 0) {
ANS[0][0] = 0;
rep(i,1,N) ANS[0][i] = 1;
rep(i,1,N-1) ANS[i][N-1] = 0;
ANS[N-1][N-1] = Z[N*2-2];
ANS[N-1][0] = 0;
ANS[N-2][0] = 1;
}
else {
ANS[0][0] = 1;
rep(i,1,N) ANS[i][0] = 0;
rep(i,1,N-1) ANS[N-1][i] = 1;
ANS[N-1][N-1] = Z[N*2-2];
ANS[0][N-1] = 1;
ANS[0][N-2] = 0;
}
vector<int> C(N*2-1,0);
rep(i,0,N) {
rep(j,0,N) {
if (ANS[i][j] != -1) C[i+j] ^= ANS[i][j];
}
}
rep(i,0,N) {
rep(j,0,N) {
if (ANS[i][j] != -1) continue;
ANS[i][j] = (C[i+j] ^ Z[i+j]);
C[i+j] ^= ANS[i][j];
}
}
}
if (!Judge(N,X,Y,Z,ANS)) return {false,ANS};
return {true,ANS};
}
bool Solve2(int N, vector<int> X, vector<int> Y, vector<int> Z) {
vector<vector<int>> ANS(N, vector<int>(N, 0));
rep(i,0,30) {
vector<int> A(N,0), B(N,0), C(N*2-1,0);
rep(j,0,N) {
if (X[j] & (1<<i)) A[j] = 1;
if (Y[j] & (1<<i)) B[j] = 1;
}
rep(j,0,N*2-1) {
if (Z[j] & (1<<i)) C[j] = 1;
}
auto [flag,ret] = Calc(N,A,B,C);
if (!flag) {
cout << -1 << endl;
return true;
}
rep(j,0,N) {
rep(k,0,N) {
if (ret[j][k] == 1) ANS[j][k] += (1<<i);
}
}
// if (i >= 0) {
// rep(j,0,N) cout << A[j];
// cout << endl;
// rep(j,0,N) cout << B[j];
// cout << endl;
// rep(j,0,N*2-1) cout << C[j];
// cout << endl;
// rep(j,0,N) {
// rep(k,0,N) {
// cout << ret[j][k] << (k+1==N?'\n':' ');
// }
// }
// }
}
rep(i,0,N) {
rep(j,0,N) {
cout << ANS[i][j] << (j+1==N?'\n':' ');
}
}
return true;
if (!Judge(N,X,Y,Z,ANS)) {
rep(i,0,N) cout << X[i] << ' ';
cout << endl;
rep(i,0,N) cout << Y[i] << ' ';
cout << endl;
rep(i,0,N*2-1) cout << Z[i] << ' ';
cout << endl;
rep(i,0,N) {
rep(j,0,N) {
cout << ANS[i][j] << ' ';
}
cout << endl;
}
return false;
}
return true;
}
bool RandomCheck() {
int N = Random::get(1,4);
vector<int> X(N), Y(N), Z(N*2-1);
rep(i,0,N) {
X[i] = Random::get(0,1);
Y[i] = Random::get(0,1);
}
rep(i,0,N*2-1) {
Z[i] = Random::get(0,1);
}
return Solve2(N,X,Y,Z);
}
void Solve() {
int N;
cin >> N;
vector<int> X(N), Y(N), Z(N*2-1);
rep(i,0,N) cin >> X[i];
rep(i,0,N) cin >> Y[i];
rep(i,0,N*2-1) cin >> Z[i];
Solve2(N,X,Y,Z);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
ll _ = 1;
cin>>_;
while(_--){
//if (!RandomCheck()) break;
Solve();
}
return 0;
}