#771026 (Rust) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: rhoo
• 提出日時: 2022-06-14 01:16:28
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 982 ms / 1,000 ms
• コード長: 11,311 bytes
• コンパイル時間: 1,350 ms
• 実行使用メモリ: 2,748 KB
• スコア: 52,795
• 最終ジャッジ日時: 2022-06-14 01:17:04
• 合計ジャッジ時間: 36,242 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	981 ms; 2,624 KB
testcase_01	AC	982 ms; 2,576 KB
testcase_02	AC	981 ms; 2,660 KB
testcase_03	AC	982 ms; 2,732 KB
testcase_04	AC	981 ms; 2,648 KB
testcase_05	AC	981 ms; 2,600 KB
testcase_06	AC	981 ms; 2,612 KB
testcase_07	AC	981 ms; 2,748 KB
testcase_08	AC	980 ms; 2,660 KB
testcase_09	AC	981 ms; 2,628 KB
testcase_10	AC	981 ms; 2,636 KB
testcase_11	AC	981 ms; 2,624 KB
testcase_12	AC	982 ms; 2,544 KB
testcase_13	AC	981 ms; 2,552 KB
testcase_14	AC	982 ms; 2,640 KB
testcase_15	AC	981 ms; 2,636 KB
testcase_16	AC	982 ms; 2,556 KB
testcase_17	AC	982 ms; 2,588 KB
testcase_18	AC	981 ms; 2,492 KB
testcase_19	AC	980 ms; 2,624 KB
testcase_20	AC	982 ms; 2,612 KB
testcase_21	AC	980 ms; 2,724 KB
testcase_22	AC	981 ms; 2,612 KB
testcase_23	AC	981 ms; 2,648 KB
testcase_24	AC	981 ms; 2,480 KB
testcase_25	AC	981 ms; 2,608 KB
testcase_26	AC	982 ms; 2,548 KB
testcase_27	AC	981 ms; 2,644 KB
testcase_28	AC	981 ms; 2,632 KB
testcase_29	AC	981 ms; 2,588 KB
testcase_30	AC	981 ms; 2,548 KB
testcase_31	AC	981 ms; 2,536 KB

コンパイルメッセージ

warning: unused variable: `p`
   --> Main.rs:450:9
    |
450 |     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:169:21
    |
169 |                     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:172:21
    |
172 |                     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:180:21
    |
180 |                     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:183:21
    |
183 |                     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

ソースコード

#[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,score:&mut i64)->bool{
        let (f,idx,mut s,mut t)=self.out[id];
        if t==N || s!=0 && rnd::next()&1==0{
            s-=1;
            t-=1;
        }
        let p1;
        let p2;

        let diff=if f{
            (p1,p2)=((idx,s),(idx,t));
            2-((self.state[idx][s] as i64+self.state[idx][t] as i64)<<1)
        }
        else{
            (p1,p2)=((s,idx),(t,idx));
            2-((self.state[s][idx] as i64+self.state[t][idx] 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,score:&mut i64)->bool{
        let mut diff=0;
        let (f1,idx1,mut s1,t1)=self.out[id1];
        let p1;
        diff+=if s1==0 || t1!=N && rnd::next()&1==0{
            if f1{
                self.state[idx1][t1]=!self.state[idx1][t1];
                p1=(idx1,t1);
                !self.state[idx1][t1]
            }
            else{
                self.state[t1][idx1]=!self.state[t1][idx1];
                p1=(t1,idx1);
                !self.state[t1][idx1]
            }
        }
        else{
            s1-=1;
            if f1{
                self.state[idx1][s1]=!self.state[idx1][s1];
                p1=(idx1,s1);
                !self.state[idx1][s1]
            }
            else{
                self.state[s1][idx1]=!self.state[s1][idx1];
                p1=(s1,idx1);
                !self.state[s1][idx1]
            }
        } as i64;

        let (f2,idx2,s2,mut t2)=self.out[id2];
        let p2;
        diff+=if rnd::next()&1==0{
            if f2{
                p2=(idx2,s2);
                self.state[idx2][s2]
            }
            else{
                p2=(s2,idx2);
                self.state[s2][idx2]
            }
        }
        else{
            t2-=1;
            if f2{
                p2=(idx2,t2);
                self.state[idx2][t2]
            }
            else{
                p2=(t2,idx2);
                self.state[t2][idx2]
            }
        } 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,score:&mut i64)->bool{
        let mut l=input.target[id];
        let nd;

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

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

    #[inline]
    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&2047==0{
            const TL:f64=0.98;
            let p=get_time()/TL;
            if p>=1.{break;}

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

            th.fill_with(||(heat*rnd::nextf().ln()) as i64);
        }
        iter+=1;

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

        let r=rnd::next();
        
        up+=if r&255==0 && input.target[idx]<=4{ out.set_best(th[iter&255],idx,input.target[idx],&mut score) }
        else if r&1==0{ out.shift(th[iter&255],idx,&mut score) }
        else{ out.swap(input,th[iter&255],idx,&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
}


fn main(){
    let (input,state)=In::input();
    let ans=sa(&input,state);

    ans.print(&input);
}