結果

問題 No.3736 Purely Bool Hell
コンテスト
ユーザー rhoo
提出日時 2026-09-19 18:03:04
言語 Rust
(1.97.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 622 ms / 3,000 ms
+ 943µs
コード長 11,614 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,087 ms
コンパイル使用メモリ 218,924 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-09-19 18:03:25
合計ジャッジ時間 11,342 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
   --> src/main.rs:513:7
    |
513 | #[cfg(feature="local")]
    |       ^^^^^^^^^^^^^^^ help: remove the condition
    |
    = note: no expected values for `feature`
    = help: consider adding `local` as a feature in `Cargo.toml`
    = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
    = note: `#[warn(unexpected_cfgs)]` on by default

warning: unexpected `cfg` condition value: `local`
   --> src/main.rs:515:11
    |
515 | #[cfg(not(feature="local"))]
    |           ^^^^^^^^^^^^^^^ help: remove the condition
    |
    = note: no expected values for `feature`
    = help: consider adding `local` as a feature in `Cargo.toml`
    = note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration

warning: unused variable: `i`
   --> src/main.rs:241:47
    |
241 |                 let &(i,j)=ps.iter().find(|&&(i,j)|isok[j]).unwrap_or(&ps[0]);
    |                                               ^ help: if this is intentional, prefix it with an underscore: `_i`
    |
    = note: `#[warn(unused_variables)]` (part of `#[warn(unused)]`) on by default

warning: unused variable: `j`
   --> src/main.rs:187:49
    |
187 |                 let &(i,j)=ps.iter().find(|&&(i,j)|isok[i]).unwrap_or(&ps.last().unwrap());
    |                                                 ^ help: if this is intentional, prefix it with an underscore: `_j`

ソースコード

diff #
raw source code 

#![allow(non_snake_case,dead_code,unused_imports)]
use proconio::{*,marker::*};



fn main(){
    input!{
        t:usize,
    }
    
    'a: for _ in 0..t{
        input!{
            n:usize,
            x:[usize;n],
            y:[usize;n],
            z:[usize;2*n-1],
        }
        
        let mut tx=vec![0;n];
        let mut ty=vec![0;n];
        let mut tz=vec![0;2*n-1];
        
        let mut ans=vec![vec![0;n];n];
        
        for i in 0..30{
            for (a,ta) in [(&x,&mut tx),(&y,&mut ty),(&z,&mut tz)]{
                for j in 0..a.len(){
                    ta[j]=a[j]>>i&1;
                }
            }
            
            if let Some(res)=solve(n,&tx,&ty,&tz){
                for p in iterp(n,n){
                    ans[p]|=res[p]<<i;
                }
            } else{
                println!("-1");
                continue 'a;
            }
        }
        
        for i in 0..n{
            println!("{}",ans[i].iter().join(" "));
        }
    }
}




fn solve(n:usize,x:&[usize],y:&[usize],z:&[usize])->Option<Vec<Vec<usize>>>{
    let all1_i=(0..n).filter(|&i|x[i]==1).collect_vec();
    let all0_j=(0..n).filter(|&j|y[j]==0).collect_vec();
    
    if all1_i.len()>0 && all0_j.len()>0{
        return None;
    }
    
    let check=|ans:&Vec<Vec<usize>>|->bool{
        for i in 0..n{
            let mut and=1;
            for j in 0..n{
                and&=ans[i][j];
            }
            if and!=x[i]{
                return false;
            }
        }
        
        for j in 0..n{
            let mut or=0;
            for i in 0..n{
                or|=ans[i][j];
            }
            if or!=y[j]{
                return false;
            }
        }
        
        for sum in 0..z.len(){
            let mut xor=0;
            for i in 0..=sum{
                let j=sum-i;
                if i<n && j<n{
                    xor^=ans[i][j];
                }
            }
            if xor!=z[sum]{
                return false;
            }
        }
        
        true
    };
    
    let mut ans=vec![vec![0;n];n];
    if all1_i.is_empty() && all0_j.is_empty(){
        if n==1{
            return None;
        }
        
        if n<=3{
            for bit in 0..1<<(n*n){
                for i in 0..n{
                    for j in 0..n{
                        ans[i][j]=bit>>(i*n+j)&1;
                    }
                }
                
                if check(&ans){
                    return Some(ans);
                }
            }
            
            return None;
        }
        
        for j in 2..n{
            ans[0][j]=1;
        }
        ans[n-2][0]=1;
        ans[n-1][1]=1;
        
        let mut p=P::new(0,0);
        let mut path=vec![p];
        for t in 1..z.len(){
            if t%2==0{
                p+=DD[2];
            } else{
                p+=DD[3];
            }
            path.push(p);
        }
        assert!(path.len()==z.len());
        
        for &p in &path{
            let sum=p.i+p.j;
            let mut xor=0;
            for i in 0..=sum{
                let j=sum-i;
                if i<n && j<n{
                    xor^=ans[i][j];
                }
            }
            
            if xor!=z[sum]{
                ans[p]^=1;
            }
        }
        
        assert!(check(&ans));
        Some(ans)
    } else if !all1_i.is_empty(){
        for &i in &all1_i{
            for j in 0..n{
                ans[i][j]=1;
            }
        }
        
        // 貪欲に埋めていく
        // できるだけ0がたくさんあると嬉しいから...
        let mut ps=vec![];
        let mut isok=vec![false;n];
        
        for sum in 0..z.len(){
            let mut xor=0;
            ps.clear();
            for i in 0..=sum{
                let j=sum-i;
                if i<n && j<n{
                    if ans[i][j]==0{
                        ps.push((i,j));
                    }
                    xor^=ans[i][j];
                }
            }
            
            if xor!=z[sum]{
                // ps のどれかを選んで flip する
                // isok 優先
                // ないなら i が最もデカいやつ
                
                if ps.is_empty(){
                    return None;
                }
                
                let &(i,j)=ps.iter().find(|&&(i,j)|isok[i]).unwrap_or(&ps.last().unwrap());
                ans[i][j]^=1;
            }
            
            for &(i,j) in &ps{
                if ans[i][j]==0{
                    isok[i]=true;
                }
            }
        }
        
        if check(&ans){
            Some(ans)
        } else{
            None
        }
    } else{
        for i in 0..n{
            for j in 0..n{
                ans[i][j]=1;
            }
        }
        
        for &j in &all0_j{
            for i in 0..n{
                ans[i][j]=0;
            }
        }
        
        let mut ps=vec![];
        let mut isok=vec![false;n];
        
        for sum in 0..z.len(){
            let mut xor=0;
            ps.clear();
            for i in 0..=sum{
                let j=sum-i;
                if i<n && j<n{
                    if ans[i][j]==1{
                        ps.push((i,j));
                    }
                    xor^=ans[i][j];
                }
            }
            
            if xor!=z[sum]{
                // ps のどれかを選んで flip する
                // isok 優先
                // ないなら j が最もデカいやつ
                
                if ps.is_empty(){
                    return None;
                }
                
                let &(i,j)=ps.iter().find(|&&(i,j)|isok[j]).unwrap_or(&ps[0]);
                ans[i][j]^=1;
            }
            
            for &(i,j) in &ps{
                if ans[i][j]==1{
                    isok[j]=true;
                }
            }
        }
        
        if check(&ans){
            Some(ans)
        } else{
            None
        }
    }
}



use std::iter::*;
use itertools::*;



trait ChangeMinMax:Copy+PartialOrd{
    fn chmin(&mut self,a:Self)->bool{
        *self>a && {
            *self=a;
            true
        }
    }
    
    fn chmax(&mut self,a:Self)->bool{
        *self<a && {
            *self=a;
            true
        }
    }
}

impl<T:Copy+PartialOrd> ChangeMinMax for T{}



// library: https://github.com/rhoo19937/cp-lib



// LURD
const DD:[P;4]=[P{i:0,j:!0},P{i:!0,j:0},P{i:0,j:1},P{i:1,j:0}];
const DX:[P;8]=[P{i:0,j:!0},P{i:!0,j:!0},P{i:!0,j:0},P{i:!0,j:1},P{i:0,j:1},P{i:1,j:1},P{i:1,j:0},P{i:1,j:!0}];

#[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash,Default)]
struct P{
    i:usize,
    j:usize,
}
impl P{
    fn new(i:usize,j:usize)->P{
        P{i,j}
    }
    
    fn in_range(self,h:usize,w:usize)->bool{
        self.i<h && self.j<w
    }
    
    fn id(self,w:usize)->usize{
        self.i*w+self.j
    }
    
    fn from(id:usize,w:usize)->P{
        P::new(id/w,id%w)
    }
    
    fn manh(self,p:P)->usize{
        let abs_diff=|a,b|(a as i64-b as i64).abs() as usize;
        abs_diff(self.i,p.i)+abs_diff(self.j,p.j)
    }
    
    fn dir(self,p:P)->usize{
        if self.i==p.i{
            if self.j-1==p.j{
                0
            } else{
                assert!(self.j+1==p.j);
                2
            }
        } else{
            if self.i-1==p.i{
                1
            } else{
                assert!(self.i+1==p.i);
                3
            }
        }
    }
}
impl std::fmt::Debug for P{
    fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{
        write!(f,"({}, {})",self.i,self.j)
    }
}
impl std::ops::Add for P{
    type Output=P;
    fn add(self,a:P)->P{
        P{
            i:self.i+a.i,
            j:self.j+a.j,
        }
    }
}
impl std::ops::Sub for P{
    type Output=P;
    fn sub(self,a:P)->P{
        P{
            i:self.i-a.i,
            j:self.j-a.j,
        }
    }
}
impl std::ops::Mul<usize> for P{
    type Output=P;
    fn mul(self,a:usize)->P{
        P{
            i:self.i*a,
            j:self.j*a,
        }
    }
}
impl std::ops::Div<usize> for P{
    type Output=P;
    fn div(self,a:usize)->P{
        P{
            i:self.i/a,
            j:self.j/a,
        }
    }
}
impl std::ops::Neg for P{
    type Output=P;
    fn neg(self)->P{
        P{
            i:self.i.wrapping_neg(),
            j:self.j.wrapping_neg(),
        }
    }
}


macro_rules! impl_p_ops{
    ($t:ty,$assign_trait:ident,$assign_func:ident,$op:tt)=>{
        impl std::ops::$assign_trait<$t> for P{
            fn $assign_func(&mut self,a:$t){
                *self=*self $ op a;
            }
        }
    }
}
impl_p_ops!(P,AddAssign,add_assign,+);
impl_p_ops!(P,SubAssign,sub_assign,-);
impl_p_ops!(usize,MulAssign,mul_assign,*);
impl_p_ops!(usize,DivAssign,div_assign,/);


macro_rules! impl_p_index{
    ($t:ty)=>{
        impl<T:std::ops::Index<usize>> std::ops::Index<P> for $t{
            type Output=T::Output;
            fn index(&self,idx:P)->&T::Output{
                &self[idx.i][idx.j]
            }
        }
        impl<T:std::ops::IndexMut<usize>> std::ops::IndexMut<P> for $t{
            fn index_mut(&mut self,idx:P)->&mut T::Output{
                &mut self[idx.i][idx.j]
            }
        }
    }
}
impl_p_index!([T]);
impl_p_index!(Vec<T>);


fn iterp(h:usize,w:usize)->impl Iterator<Item=P>{
    (0..h).map(move|i|(0..w).map(move|j|P::new(i,j))).flatten()
}



#[allow(unused)]
mod rnd{
    static mut X2:u32=12345;
    static mut X3:u32=0xcafef00d;
    static mut C_X1:u64=0xd15ea5e5<<32|23456;
    
    pub fn set_seed(seed:u64){
        unsafe{
            C_X1^=seed as u64;
        }
    }
    
    pub fn next()->u32{
        unsafe{
            let x=X3 as u64*3487286589;
            let ret=(X3^X2)+(C_X1 as u32^(x>>32) as u32);
            X3=X2;
            X2=C_X1 as u32;
            C_X1=x+(C_X1>>32);
            ret
        }
    }
    
    pub fn next64()->u64{
        (next() as u64)<<32|next() as u64
    }
    
    pub fn nextf()->f64{
        f64::from_bits(0x3ff0000000000000|(next() as u64)<<20)-1.
    }
    
    pub fn get(n:usize)->usize{
        assert!(0<n && n<=u32::MAX as usize);
        next() as usize*n>>32
    }
    
    pub fn range(a:usize,b:usize)->usize{
        assert!(a<b);
        get(b-a)+a
    }
    
    pub fn range_skip(a:usize,b:usize,skip:usize)->usize{
        assert!(a<=skip && skip<b);
        let n=range(a,b-1);
        n+(skip<=n) as usize
    }
    
    pub fn rangei(a:i64,b:i64)->i64{
        assert!(a<b);
        get((b-a) as usize) as i64+a
    }
    
    pub fn shuffle<T>(a:&mut [T]){
        for i in (1..a.len()).rev(){
            a.swap(i,get(i+1));
        }
    }
    
    pub fn shuffle_iter<T:Copy>(a:&mut [T])->impl Iterator<Item=T>{
        (0..a.len()).rev().map(|i|{
            a.swap(i,get(i+1));
            a[i]
        })
    }
}


#[allow(unused)]
trait RandomChoice{
    type Output;
    fn choice(&self)->&Self::Output;
}
impl<T> RandomChoice for [T]{
    type Output=T;
    fn choice(&self)->&T{
        &self[rnd::get(self.len())]
    }
}



#[cfg(feature="local")]
include!(concat!(env!("HOME"), "/cp/lib/debug_mod.rs"));
#[cfg(not(feature="local"))]
#[macro_export]macro_rules! debug{($($t:tt)*)=>{}}



fn bit_iter(mut n:usize)->impl Iterator<Item=usize>{
    std::iter::from_fn(move||{
        if n==0{
            return None;
        }
        let i=n.trailing_zeros() as usize;
        n^=1<<i;
        Some(i)
    })
}
0