#1188368 (Rust) No.3732 Labyrinth Maker

• 問題: No.3732 Labyrinth Maker
• ユーザー: rhoo
• 提出日時: 2026-09-19 14:04:05
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 131 ms / 2,000 ms
• コード長: 6,160 bytes
• コンパイル時間: 7,099 ms
• コンパイル使用メモリ: 210,796 KB
• 実行使用メモリ: 56,168 KB
• 最終ジャッジ日時: 2026-09-19 14:04:46
• 合計ジャッジ時間: 33,035 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 59

ソースコード

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



fn main(){
    input!{
        t:usize,
    }
    
    for _ in 0..t{
        solve();
    }
}



fn solve(){
    input!{
        n:usize,
        a:[[usize;n];n],
    }
    
    let mut sum=0;
    for p in iterp(n,n){
        sum+=a[p];
    }
    
    if sum%n!=0{
        println!("-1");
        return;
    }
    
    let mut ans=vec![vec![!0;n];n];
    
    if n%2==0{
        let cyc=cycle(P::new(0,0),P::new(n,n));
        let mut sum=vec![vec![];n];
        let mut cur=0;
        for (idx,&p) in cyc.iter().enumerate(){
            sum[cur%n].push(idx);
            cur+=a[p];
        }
        
        let mut is=sum.into_iter().max_by_key(|t|t.len()).unwrap();
        is.truncate(n);
        assert!(is.len()==n);
        
        let mut it=1;
        for w in is.windows(2){
            for &p in &cyc[w[0]..w[1]]{
                ans[p]=it;
            }
            it+=1;
        }
        
        for &p in chain!(&cyc[is[n-1]..],&cyc[..is[0]]){
            ans[p]=it;
        }
    } else{
        let mut cyc=cycle(P::new(1,0),P::new(n,n));
        cyc.push(P::new(0,0));
        cyc.push(P::new(0,1));
        
        let mut chi=vec![vec![P::new(!0,!0);n];n];
        for i in 2..n{
            chi[1][i]=P::new(0,i);
        }
        
        let mut sum=vec![vec![];n];
        let mut cur=0;
        for (idx,&p) in cyc.iter().enumerate(){
            sum[cur%n].push(idx);
            cur+=a[p];
            if chi[p].in_range(n,n){
                cur+=a[chi[p]];
            }
        }
        
        let mut is=sum.into_iter().max_by_key(|t|t.len()).unwrap();
        is.truncate(n);
        assert!(is.len()==n);
        
        let mut it=1;
        for w in is.windows(2){
            for &p in &cyc[w[0]..w[1]]{
                ans[p]=it;
                if chi[p].in_range(n,n){
                    ans[chi[p]]=it;
                }
            }
            it+=1;
        }
        
        for &p in chain!(&cyc[is[n-1]..],&cyc[..is[0]]){
            ans[p]=it;
            if chi[p].in_range(n,n){
                ans[chi[p]]=it;
            }
        }
    }
    
    for i in 0..n{
        println!("{}",ans[i].iter().join(" "));
    }
}



fn cycle(p:P,q:P)->Vec<P>{
    assert!((p.i-q.i)%2==0);
    
    let mut cyc=vec![];
    for i in (p.i..q.i).step_by(2){
        for j in p.j+1..q.j{
            cyc.push(P::new(i,j));
        }
        for j in (p.j+1..q.j).rev(){
            cyc.push(P::new(i+1,j));
        }
    }
    
    for i in (p.i..q.i).rev(){
        cyc.push(P::new(i,p.j));
    }
    
    cyc
}



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 parity(self)->bool{
        (self.i^self.j)%2==1
    }
    
    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()
}