結果
| 問題 | No.3736 Purely Bool Hell |
| コンテスト | |
| ユーザー |
 Rubikun
|
| 提出日時 | 2026-09-19 17:59:52 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 6,359 bytes |
| 記録 | |
| コンパイル時間 | 1,766 ms |
| コンパイル使用メモリ | 235,648 KB |
| 実行使用メモリ | 6,528 KB |
| 最終ジャッジ日時 | 2026-09-19 18:00:58 |
| 合計ジャッジ時間 | 12,300 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge5_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 20 WA * 9 RE * 9 TLE * 1 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
bool check(vvi A,vi X,vi Y,vi Z){
int N=si(X);
for(int i=0;i<N;i++){
int z=1;
for(int j=0;j<N;j++) z&=A[i][j];
if(X[i]!=z) return false;
}
for(int j=0;j<N;j++){
int z=0;
for(int i=0;i<N;i++) z|=A[i][j];
if(Y[j]!=z) return false;
}
vi W(N+N-1);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
W[i+j]^=A[i][j];
}
}
return W==Z;
}
vvi solve(vi X,vi Y,vi Z){
int N=si(X);
if(N<=2){
for(int bit=0;bit<(1<<(N*N));bit++){
vvi A(N,vi(N));
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(bit&(1<<(i*N+j))) A[i][j]=1;
}
}
if(check(A,X,Y,Z)) return A;
}
return {};
}
if(count(all(X),1)){
if(count(all(Y),0)){
return {{}};
}else{
vvi A(N,vi(N));
for(int i=0;i<N;i++){
if(X[i]==1){
for(int j=0;j<N;j++){
A[i][j]=1;
}
}
}
vi CN(N);
for(int t=0;t<N+N-1;t++){
int l=t-(N-1),r=t;
chmax(l,0);
chmin(r,N-1);
int sum=0;
for(int i=l;i<=r;i++) sum^=(A[i][t-i]);
if(sum!=Z[t]){
for(int i=l;i<=r;i++){
if(A[i][t-i]==0){
if(CN[i]<N){
A[i][t-i]=1;
CN[i]++;
break;
}
}
}
}
}
if(check(A,X,Y,Z)) return A;
else return {};
}
}else{
if(count(all(Y),0)){
vvi A(N,vi(N,1));
for(int j=0;j<N;j++){
if(Y[j]==0){
for(int i=0;i<N;i++){
A[i][j]=0;
}
}
}
vi CN(N);
for(int t=0;t<N+N-1;t++){
int l=t-(N-1),r=t;
chmax(l,0);
chmin(r,N-1);
int sum=0;
for(int j=l;j<=r;j++) sum^=(A[t-j][j]);
if(sum!=Z[t]){
for(int j=l;j<=r;j++){
if(A[t-j][j]==1){
if(CN[j]<N){
A[t-j][j]=0;
CN[j]++;
break;
}
}
}
}
}
if(check(A,X,Y,Z)) return A;
else return {};
}else{
vvi A(N,vi(N,-1));
A[0][0]=Z[0];
A[N-1][N-1]=Z.back();
A[2][0]=1;
A[N-1][N-3]=0;
if(A[0][0]==0){
A[0][N-1]=1;
for(int j=1;j<N-1;j++) A[0][j]=1;
for(int i=1;i<N-1;i++) A[i][N-1]=0;
}else if(A[N-1][N-1]==1){
A[0][N-1]=0;
for(int j=1;j<N-1;j++) A[0][j]=1;
for(int i=1;i<N-1;i++) A[i][N-1]=0;
}else{
A[0][1]=1;
A[1][1]=1;
for(int j=2;j<N;j++) A[0][j]=1;
for(int i=1;i<N-1;i++) A[i][N-1]=0;
}
for(int t=0;t<N+N-1;t++){
int l=t-(N-1),r=t;
chmax(l,0);
chmin(r,N-1);
int sum=0;
vii ch;
for(int j=l;j<=r;j++){
if(A[t-j][j]==-1){
ch.pb(mp(t-j,j));
A[t-j][j]=0;
}else{
sum^=A[t-j][j];
}
}
if(sum!=Z[t]&&si(ch)){
A[ch.back().fi][ch.back().se]=1;
}
}
if(check(A,X,Y,Z)) return A;
else return {};
}
}
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int Q;cin>>Q;
while(Q--){
int N;cin>>N;
vi X(N),Y(N),Z(2*N-1);
for(int i=0;i<N;i++){
cin>>X[i];
}
for(int i=0;i<N;i++){
cin>>Y[i];
}
for(int i=0;i<2*N-1;i++){
cin>>Z[i];
}
vvi ans(N,vi(N));
bool ok=true;
for(int t=0;t<30;t++){
vi x(N),y(N),z(2*N-1);
for(int i=0;i<N;i++){
if(X[i]&(1<<t)) x[i]=1;
}
for(int i=0;i<N;i++){
if(Y[i]&(1<<t)) y[i]=1;
}
for(int i=0;i<2*N-1;i++){
if(Z[i]&(1<<t)) z[i]=1;
}
auto res=solve(x,y,z);
if(si(res)==0){
ok=false;
break;
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(res[i][j]) ans[i][j]|=(1<<t);
}
}
}
if(ok){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout<<ans[i][j]<<" ";
}
cout<<"\n";
}
}else{
cout<<-1<<"\n";
}
}
}