結果
| 問題 | No.3736 Purely Bool Hell |
| コンテスト | |
| ユーザー |
 Rice_tawara459
|
| 提出日時 | 2026-09-19 17:38:50 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 577 ms / 3,000 ms |
| + 244µs | |
| コード長 | 8,149 bytes |
| 記録 | |
| コンパイル時間 | 2,379 ms |
| コンパイル使用メモリ | 365,908 KB |
| 実行使用メモリ | 7,424 KB |
| 最終ジャッジ日時 | 2026-09-19 17:39:07 |
| 合計ジャッジ時間 | 13,560 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 39 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
return os<<p.first<<' '<<p.second;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
if (a.empty()) return os;
os << a.front();
for (auto e : a | views::drop(1)){
os << ' ' << e;
}
return os;
}
void dump(auto ...vs){
((cout << vs << ' '), ...) << endl;
}
pair<bool,vector<vector<int>>> solve_one(vector<int> X,vector<int> Y,vector<int> Z){
ll N=X.size();
vector A(N,vector<int>(N,0));
if (N<=3){
rep(bi,1<<(N-1)*(N-1)){
rep(i,N){
rep(j,N){
A[i][j]=0;
}
}
for (ll i=1;i<N;i++){
for (ll j=0;j<N-1;j++){
A[i][j]=bi>>((i-1)*(N-1)+j)&1;
ll t=i+j;
if (t<N){
A[0][t]^=A[i][j];
}
else{
A[t-N+1][N-1]^=A[i][j];
}
}
}
rep(t,2*N-1){
if (t<N){
A[0][t]^=Z[t];
}
else{
A[t-N+1][N-1]^=Z[t];
}
}
bool flag=true;
rep(i,N){
int res=1;
rep(j,N){
res&=A[i][j];
}
if (res!=X[i])flag=false;
}
rep(j,N){
int res=0;
rep(i,N){
res|=A[i][j];
}
if (res!=Y[j])flag=false;
}
if (flag){
return {true,A};
}
}
return {false,{}};
}
bool fx=(*max_element(all(X))==1);
bool fy=(*min_element(all(Y))==0);
if (fx and fy){
return {false,{}};
}
if (not (fx or fy)){
rep(i,N){
rep(j,N){
ll d=(2*N+j-i)%(2*N);
if (d==0 or d==1){
A[i][j]=Z[i+j];
continue;
}
A[i][j]=d%2;
}
}
rep(i,N){
rep(j,N){
ll d=(2*N+j-i)%(2*N);
if (d==0 or d==1){
continue;
}
ll m=(i+j)/2;
ll r=(i+j)%2;
// dump(i,j,m,r);
A[m][m+r]^=A[i][j];
}
}
return {true,A};
}
if ((not fx) and fy){
rep(i,N)rep(j,N)A[i][j]=-1;
vector<bool> oky(N,false);
rep(j,N){
if (Y[j]==0){
rep(i,N){
A[i][j]=0;
}
oky[j]=true;
}
}
rep(k,2*N-1){
ll siwa=-1;
ll r=0;
rep(j,N){
ll i=k-j;
if (i>=N)continue;
if (i<0)continue;
if (A[i][j]!=-1){
r^=A[i][j];
continue;
}
}
rep(j,N){
ll i=k-j;
if (i>=N)continue;
if (i<0)continue;
if (A[i][j]==-1){
siwa=j;
if (oky[j]){
break;
}
continue;
}
}
if (siwa==-1)continue;
rep(j,N){
ll i=k-j;
if (i>=N)continue;
if (i<0)continue;
if (j==siwa)continue;
if (A[i][j]==-1){
A[i][j]=1;
oky[j]=true;
r^=1;
continue;
}
}
{
ll j=siwa;
ll i=k-j;
A[i][j]=Z[k]^r;
if (A[i][j]==1){
oky[j]=true;
}
}
}
}
if (fx and (not fy)){
rep(i,N)rep(j,N)A[i][j]=-1;
vector<bool> okx(N,false);
rep(i,N){
if (X[i]==1){
rep(j,N){
A[i][j]=1;
}
okx[i]=true;
}
}
rep(k,2*N-1){
// rep(i,N){
// dump(A[i]);
// }
ll siwa=-1;
ll r=0;
rep(i,N){
ll j=k-i;
if (j>=N)continue;
if (j<0)continue;
if (A[i][j]!=-1){
r^=A[i][j];
continue;
}
}
rep(i,N){
ll j=k-i;
if (j>=N)continue;
if (j<0)continue;
if (A[i][j]==-1){
siwa=i;
if (okx[i]){
break;
}
continue;
}
}
if (siwa==-1)continue;
rep(i,N){
ll j=k-i;
if (j>=N)continue;
if (j<0)continue;
if (i==siwa)continue;
if (A[i][j]==-1){
A[i][j]=0;
okx[i]=true;
r^=0;
continue;
}
}
{
ll i=siwa;
ll j=k-i;
A[i][j]=Z[k]^r;
if (A[i][j]==0){
okx[i]=true;
}
}
}
}
vector<int> rx(N,1),ry(N,0),rz(2*N-1,0);
rep(i,N){
rep(j,N){
assert(A[i][j]==0 or A[i][j]==1);
rx[i]&=A[i][j];
ry[j]|=A[i][j];
rz[i+j]^=A[i][j];
}
}
bool flag=true;
if (rx!=X)flag=false;
if (ry!=Y)flag=false;
if (ry!=Y)flag=false;
if (flag){
return {true,A};
}
else{
return {false,{}};
}
}
void solve() {
ll N;
cin>>N;
vector<ll> X(N),Y(N),Z(2*N-1);
rep(i,N)cin>>X[i];
rep(i,N)cin>>Y[i];
rep(i,2*N-1)cin>>Z[i];
vector A(N,vector<ll> (N,0));
bool flag=true;
rep(d,31){
vector<int> dx(N),dy(N),dz(2*N-1);
rep(i,N){
dx[i]=X[i]>>d&1;
}
rep(j,N){
dy[j]=Y[j]>>d&1;
}
rep(k,2*N-1){
dz[k]=Z[k]>>d&1;
}
auto res=solve_one(dx,dy,dz);
if (!res.first){
flag=false;
continue;
}
rep(i,N){
rep(j,N){
A[i][j]|=res.second[i][j]<<d;
}
}
}
if (!flag){
cout<<-1<<'\n';
return;
}
vector<ll> rx(N,-1);
vector<ll> ry(N,0);
rep(i,N){
rep(j,N){
Z[i+j]^=A[i][j];
rx[i]&=A[i][j];
ry[j]|=A[i][j];
}
}
if (X!=rx or Y!=ry or *max_element(all(Z))!=0){
cout<<-1<<'\n';
return;
}
rep(i,N){
cout<<A[i]<<'\n';
}
// assert(X==rx);
// assert(Y==ry);
// if (*max_element(all(Z))!=0){
// dump("NG");
// assert(false);
// }
return;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
ll T=1;
cin>>T;
while (T--){
solve();
}
return 0;
}