#771165 (Rust) No.5002 stick xor

提出ソース

結果

問題	No.5002 stick xor
ユーザー	rhoo
提出日時	2022-06-14 23:10:57
言語	Rust (1.77.0)
結果	AC
実行時間	992 ms / 1,000 ms
コード長	12,806 bytes
コンパイル時間	1,219 ms
実行使用メモリ	5,160 KB
スコア	52,887
最終ジャッジ日時	2022-06-14 23:11:35
合計ジャッジ時間	36,364 ms
ジャッジサーバーID （参考情報）	judge14 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	991 ms 2,528 KB
testcase_01	AC	992 ms 2,736 KB
testcase_02	AC	991 ms 3,120 KB
testcase_03	AC	992 ms 3,116 KB
testcase_04	AC	990 ms 3,112 KB
testcase_05	AC	991 ms 3,112 KB
testcase_06	AC	991 ms 3,116 KB
testcase_07	AC	992 ms 3,120 KB
testcase_08	AC	992 ms 3,116 KB
testcase_09	AC	992 ms 3,116 KB
testcase_10	AC	992 ms 3,112 KB
testcase_11	AC	991 ms 3,116 KB
testcase_12	AC	992 ms 3,120 KB
testcase_13	AC	992 ms 3,112 KB
testcase_14	AC	992 ms 3,112 KB
testcase_15	AC	991 ms 3,116 KB
testcase_16	AC	992 ms 3,112 KB
testcase_17	AC	991 ms 3,116 KB
testcase_18	AC	992 ms 3,112 KB
testcase_19	AC	992 ms 3,116 KB
testcase_20	AC	992 ms 3,116 KB
testcase_21	AC	992 ms 4,900 KB
testcase_22	AC	992 ms 4,904 KB
testcase_23	AC	992 ms 5,156 KB
testcase_24	AC	992 ms 4,900 KB
testcase_25	AC	991 ms 4,904 KB
testcase_26	AC	991 ms 5,160 KB
testcase_27	AC	991 ms 4,904 KB
testcase_28	AC	992 ms 4,904 KB
testcase_29	AC	992 ms 4,904 KB
testcase_30	AC	991 ms 5,156 KB
testcase_31	AC	991 ms 4,904 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused variable: `p`
   --> Main.rs:488:9
    |
488 |     let p=up as f64/iter as f64;
    |         ^ help: if this is intentional, prefix it with an underscore: `_p`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused `Result` that must be used
   --> Main.rs:168:21
    |
168 |                     writeln!(stdout,"{} {} {} {}",y,x,y,x);
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(unused_must_use)]` on by default
    = note: this `Result` may be an `Err` variant, which should be handled
    = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: unused `Result` that must be used
   --> Main.rs:171:21
    |
171 |                     writeln!(stdout,"1 1 1 1");
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: this `Result` may be an `Err` variant, which should be handled
    = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: unused `Result` that must be used
   --> Main.rs:179:21
    |
179 |                     writeln!(stdout,"{} {} {} {}",id,s,id,t);
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: this `Result` may be an `Err` variant, which should be handled
    = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: unused `Result` that must be used
   --> Main.rs:182:21
    |
182 |                     writeln!(stdout,"{} {} {} {}",s,id,t,id);
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: this `Result` may be an `Err` variant, which should be handled
    = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: 5 warnings emitted

ソースコード

raw source code

#[allow(unused)]
mod rnd {
    static mut S:usize=88172645463325252;
    #[inline]
    pub fn next()->usize{
        unsafe{
            S=S^S<<7;
            S=S^S>>9;
            S
        }
    }

    #[inline]
    pub fn nextf()->f64{
        (next()&4294967295) as f64/4294967296.
    }
}


#[allow(unused)]
#[inline]
fn get_time()->f64{
    static mut START:f64=-1.;
    let t=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
    unsafe{
        if START<0.{START=t;}
        t-START
    }
}


#[cfg(local)]
#[allow(unused)]
macro_rules! debug{
    ($x:expr)=>{
        eprintln!("{}: {:?}",stringify!($x),$x);
    };
    
    ($x:expr,$($l:expr),*)=>{
        eprint!("{}: {:?}, ",stringify!($x),$x);
        debug!($($l),*);
    }
}
#[cfg(not(local))]
#[allow(unused)]
macro_rules! debug{
    ($($_:expr),*)=>{}
}


const N:usize=60;
const K:usize=500;

const M:usize=26;


struct In{
    l:[usize;K],
    target:Vec<usize>,
    len:[Vec<usize>;M]
}
impl In{
    fn input()->(In,[[bool;N];N]){
        use std::io::Read;
        
        let mut input="".to_owned();
        std::io::stdin().read_to_string(&mut input).unwrap();
        let mut input=input.split_ascii_whitespace();
        macro_rules! read(($ty:ty) => (input.next().unwrap().parse::<$ty>().unwrap()));

        let n=read!(usize);
        let k=read!(usize);
        assert_eq!((n,k),(N,K));

        let mut l=[!0;K];
        let mut target=vec![];
        let mut len=[();M].map(|_|vec![]);
        for i in 0..K{
            let length=read!(usize);
            l[i]=length;
            if length!=1{
                len[length].push(target.len());
                target.push(length);
            }
        }

        let mut grid=[[false;N];N];
        for i in 0..N{
            let s=read!(String);
            for (j,v) in s.chars().enumerate(){
                grid[i][j]=v=='0';
            }
        }

        (In{l,target,len},grid)
    }
}


struct Out{
    state:[[bool;N];N],
    out:Vec<(bool,usize,usize,usize)>, // $0==true := 横向き ($2,$3) := (始点,終点)
    temp:[(bool,usize);N*2]
}
impl Out{
    #[inline]
    fn new(input:&In,mut state:[[bool;N];N])->Out{
        let mut out=vec![];

        for &l in input.target.iter(){
            let idx=rnd::next()%N;
            let s=rnd::next()%(N-l);
            let t=s+l;
            let f=rnd::next()&1==0;

            out.push((f,idx,s,t));
            for j in s..t{
                if f{
                    state[idx][j]=!state[idx][j];
                }
                else{
                    state[j][idx]=!state[j][idx];
                }
            }
        }

        let mut temp=[(false,!0);N*2];
        for i in 0..N*2{
            temp[i].0=i<N;
            temp[i].1=i%N;
        }

        Out{state,out,temp}
    }

    #[inline]
    // 白マスの個数
    fn score(&self)->i64{
        let mut ret=0;
        for i in 0..N{
            for j in 0..N{
                ret+=self.state[i][j] as i64;
            }
        }
        ret
    }

    #[inline]
    fn print(&self,input:&In){
        use std::io::Write;

        let stdout=std::io::stdout();
        let stdout=&mut std::io::BufWriter::new(stdout.lock());

        let mut kuro=vec![];
        for i in 0..N{
            for j in 0..N{
                if !self.state[i][j]{
                    kuro.push((i+1,j+1));
                }
            }
        }

        let mut idx=0;
        for &l in input.l.iter(){
            if l==1{
                if let Some((y,x))=kuro.pop(){
                    writeln!(stdout,"{} {} {} {}",y,x,y,x);
                }
                else{
                    writeln!(stdout,"1 1 1 1");
                }
            }
            else{
                let (f,id,s,t)=self.out[idx];
                let id=id+1;
                let s=s+1;
                if f{
                    writeln!(stdout,"{} {} {} {}",id,s,id,t);
                }
                else{
                    writeln!(stdout,"{} {} {} {}",s,id,t,id);
                }
                idx+=1;
            }
        }

        stdout.flush().unwrap();
    }
}


impl Out{
    #[inline]
    fn shift(&mut self,add:i64,id:usize,rnd:usize,score:&mut i64)->bool{
        let (f,idx,mut s,mut t)=self.out[id];
        if t==N || s!=0 && rnd&1==0{
            s-=1;
            t-=1;
        }

        let (p1,p2)=if f{((idx,s),(idx,t))}
        else{((s,idx),(t,idx))};

        let diff=2-((self.state[p1.0][p1.1] as i64+self.state[p2.0][p2.1] as i64)<<1);

        if add<=diff{
            *score+=diff;

            self.state[p1.0][p1.1]=!self.state[p1.0][p1.1];
            self.state[p2.0][p2.1]=!self.state[p2.0][p2.1];

            let a=(((self.out[id].2==s) as usize)<<1)-1;
            self.out[id].2+=a;
            self.out[id].3+=a;

            true
        }
        else{
            false
        }
    }
    
    #[inline]
    // l+1 == len(id1)+1 == len(id2)
    fn swap_sub(&mut self,add:i64,l:usize,id1:usize,id2:usize,rnd:usize,score:&mut i64)->bool{
        let (f1,idx1,mut s1,t1)=self.out[id1];
        let p1=if s1==0 || t1!=N && rnd&9007199254740992==0{
            if f1{(idx1,t1)}
            else{(t1,idx1)}
        }
        else{
            s1-=1;
            if f1{(idx1,s1)}
            else{(s1,idx1)}
        };

        let mut diff=self.state[p1.0][p1.1] as i64;
        self.state[p1.0][p1.1]=!self.state[p1.0][p1.1];

        let (f2,idx2,s2,mut t2)=self.out[id2];
        let p2=if rnd&4503599627370496==0{
            if f2{(idx2,s2)}
            else{(s2,idx2)}
        }
        else{
            t2-=1;
            if f2{(idx2,t2)}
            else{(t2,idx2)}
        };

        diff+=self.state[p2.0][p2.1] as i64;

        let diff=(1-diff)<<1;

        if add<=diff{
            *score+=diff;
            self.state[p2.0][p2.1]=!self.state[p2.0][p2.1];

            self.out.swap(id1,id2);
            (self.out[id1].2,self.out[id1].3)=(t2-l,t2);
            (self.out[id2].2,self.out[id2].3)=(s1,s1+l+1);
            
            true
        }
        else{
            self.state[p1.0][p1.1]=!self.state[p1.0][p1.1];
            
            false
        }
    }

    #[inline]
    fn swap(&mut self,input:&In,add:i64,mut id:usize,rnd:usize,score:&mut i64)->bool{
        let mut l=input.target[id];
        let nd;

        if l==2 || l!=M-1 && rnd&9007199254740992==0{
            let kouho=&input.len[l+1];
            nd=kouho[rnd%kouho.len()]
        }
        else{
            l-=1;
            let kouho=&input.len[l];
            nd=id;
            id=kouho[rnd%kouho.len()]
        }

        self.swap_sub(add,l,id,nd,rnd,score)
    }

    #[inline]
    // len(id)==2
    fn xpose(&mut self,add:i64,id:usize,r:usize,score:&mut i64)->bool{
        let (f,idx,s,t)=self.out[id];
        let t=t-1;

        let (p1,p2)=if f{
            if idx==0 || idx!=N-1 && r&2==0{
                if r&1==0{((idx,s),(idx+1,t))}
                else{((idx,t),(idx+1,s))}
            }
            else{
                if r&1==0{((idx,s),(idx-1,t))}
                else{((idx,t),(idx-1,s))}
            }
        }
        else{
            if idx==0 || idx!=N-1 && r&2==0{
                if r&1==0{((s,idx),(t,idx+1))}
                else{((t,idx),(s,idx+1))}
            }
            else{
                if r&1==0{((s,idx),(t,idx-1))}
                else{((t,idx),(s,idx-1))}
            }
        };

        let diff=2-((self.state[p1.0][p1.1] as i64+self.state[p2.0][p2.1] as i64)<<1);

        if add<=diff{
            *score+=diff;
            
            self.out[id].0=!f;
            (self.out[id].1,self.out[id].2,self.out[id].3)=if f{
                let t=idx.min(p2.0);
                (p2.1,t,t+2)
            }
            else{
                let t=idx.min(p2.1);
                (p2.0,t,t+2)
            };

            self.state[p1.0][p1.1]=!self.state[p1.0][p1.1];
            self.state[p2.0][p2.1]=!self.state[p2.0][p2.1];

            true
        }
        else{
            false
        }
    }

    fn set_best(&mut self,add:i64,id:usize,r:usize,score:&mut i64)->bool{
        let cur=(self.out[id].0,self.out[id].1);
        let (s,t)=(self.out[id].2,self.out[id].3);

        let mut before=0;
        if cur.0{
            for i in s..t{
                before+=1-((self.state[cur.1][i] as i64)<<1);
                self.state[cur.1][i]=!self.state[cur.1][i];
            }
        }
        else{
            for i in s..t{
                before+=1-((self.state[i][cur.1] as i64)<<1);
                self.state[i][cur.1]=!self.state[i][cur.1];
            }
        }

        for i in (0..N<<1).rev(){
            self.temp.swap(i,rnd::next()%(i+1));
            let (f,idx)=self.temp[i];

            if cur!=(f,idx){
                let mut diff=before;
                if f{
                    for j in 0..r{
                        diff+=1-((self.state[idx][j] as i64)<<1);
                    }
                    let mut p=0;

                    while{
                        if add<=diff{
                            self.out[id]=(f,idx,p,r+p);
                            *score+=diff;

                            for i in p..r+p{
                                self.state[idx][i]=!self.state[idx][i];
                            }

                            return true;
                        }
                        p<N-r
                    }{
                        diff+=(self.state[idx][p] as i64-self.state[idx][r+p] as i64)<<1;
                        p+=1;
                    }
                }
                else{
                    for j in 0..r{
                        diff+=1-((self.state[j][idx] as i64)<<1);
                    }
                    let mut p=0;

                    while{
                        if add<=diff{
                            self.out[id]=(f,idx,p,r+p);
                            *score+=diff;

                            for i in p..r+p{
                                self.state[i][idx]=!self.state[i][idx];
                            }
                            
                            return true;
                        }
                        p<N-r
                    }{
                        diff+=(self.state[p][idx] as i64-self.state[p+r][idx] as i64)<<1;
                        p+=1;
                    }
                }
            }
        }

        if cur.0{
            for i in s..t{
                self.state[cur.1][i]=!self.state[cur.1][i];
            }
        }
        else{
            for i in s..t{
                self.state[i][cur.1]=!self.state[i][cur.1];
            }
        }

        false
    }
}


fn sa(input:&In,state:[[bool;N];N])->Out{
    let mut out=Out::new(input,state);
    let mut score=out.score();
    let mut best=score;

    let mut iter=0;
    let mut up=0;
    let mut th=[0;256];

    let mut idx=0;

    loop{
        if iter&16383==0{
            #[cfg(local)]
            const TL:f64=0.5;
            #[cfg(not(local))]
            const TL:f64=0.99;
            
            let p=get_time()/TL;
            if p>=1.{break;}

            const T:f64=0.8;
            let heat=T*(1.-p);

            for i in 0..128{
                let r=rnd::next();
                th[i<<1]=(((r&4294967295) as f64/4294967296.).ln()*heat) as i64;
                th[(i<<1)+1]=(((r>>32) as f64/4294967296.).ln()*heat) as i64;
            }
        }
        iter+=1;

        idx+=1;
        if idx==input.target.len(){idx=0;}

        let r=rnd::next();
        
        up+=if r&18374686479671623680==0 && input.target[idx]<=4{
            out.set_best(th[iter&255],idx,input.target[idx],&mut score)
        }
        else if r&54043195528445952==0{
            if input.target[idx]==2 && r&9007199254740992==0{
                out.xpose(th[iter&255],idx,r,&mut score)
            }
            else{
                out.shift(th[iter&255],idx,r,&mut score)
            }
        }
        else{
            out.swap(input,th[iter&255],idx,r,&mut score)
        } as usize;

        best=best.max(score);
    }

    let p=up as f64/iter as f64;
    debug!(iter,p);
    debug!(score,best);
    assert_eq!(score,out.score());

    out
}


#[cfg(local)]
fn main(){
    let (input,state)=In::input();
    let mut before=0;
    for i in 0..N{
        for j in 0..N{
            if state[i][j]{
                before+=1;
            }
        }
    }
    
    let ans=sa(&input,state);

    let mut score=ans.score();
    for &l in input.l.iter(){
        if l==1{score+=1;}
    }
    score-=before;

    eprintln!("{score}");
    ans.print(&input);
}


#[cfg(not(local))]
fn main(){
    let (input,state)=In::input();
    let ans=sa(&input,state);
    ans.print(&input);
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード