#776535 (Rust) No.5005 3-SAT

• 問題: No.5005 3-SAT
• ユーザー: rhoo
• 提出日時: 2022-07-07 19:47:20
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 1,983 ms / 2,000 ms
• コード長: 5,984 bytes
• コンパイル時間: 830 ms
• 実行使用メモリ: 3,272 KB
• スコア: 108,354
• 最終ジャッジ日時: 2022-07-07 19:50:47
• 合計ジャッジ時間: 205,159 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

ファイルパターン	結果
other	AC * 100

コンパイルメッセージ

warning: unused variable: `p`
   --> Main.rs:236:9
    |
236 |     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: variable `iter` is assigned to, but never used
   --> Main.rs:253:13
    |
253 |     let mut iter=0;
    |             ^^^^
    |
    = note: consider using `_iter` instead

warning: unused variable: `out`
   --> Main.rs:282:13
    |
282 |     let mut out=Out::new();
    |             ^^^ help: if this is intentional, prefix it with an underscore: `_out`

warning: variable does not need to be mutable
   --> Main.rs:282:9
    |
282 |     let mut out=Out::new();
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: 4 warnings emitted

ソースコード

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, Chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, Usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


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


#[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=256;
const M:usize=2048;


struct In{
    edge:[[Vec<usize>;2];N]
}
impl In{
    fn input()->In{
        input!{
            q:[([usize;3],[usize;3]);M]
        }

        let mut edge=[();N].map(|_|[vec![],vec![]]);
        for (i,v) in q.iter().enumerate(){
            for (id,f) in v.0.iter().zip(v.1.iter()){
                edge[*id][*f].push(i);
            }
        }

        In{edge}
    }
}


struct Out{
    out:[bool;N],
    cnt:[usize;M],
    edge:[[Vec<usize>;2];N]
}
impl Out{
    #[inline]
    // cnt,edgeの計算はしない
    fn new()->Out{
        let mut out=[false;N];
        let mut r=!0;
        for i in 0..N{
            if i&63==0{
                r=rnd::next();
            }
            out[i]=r&1==0;
            r>>=1;
        }

        Out{out,cnt:[0;M],edge:[();N].map(|_|[vec![],vec![]])}
    }

    #[inline]
    fn re(&mut self,input:&In,r:usize){
        self.cnt.fill(0);
        for i in 0..N{
            for j in 0..2{
                self.edge[i][j].clear();
                
                for k in input.edge[i][j].iter(){
                    if *k<r{
                        self.edge[i][j].push(*k);
                    }
                }
            }

            for j in self.edge[i][self.out[i] as usize].iter(){
                self.cnt[*j]+=1;
            }
        }
    }
    
    #[inline]
    fn score(&mut self)->i64{
        self.cnt.iter().map(|x|(*x!=0) as i64).sum()
    }
    
    #[inline]
    fn change(&mut self,add:i64,idx:usize,score:&mut i64)->bool{
        let mut diff=0;
        let f=self.out[idx];
        for i in self.edge[idx][f as usize].iter(){
            self.cnt[*i]-=1;
            diff-=(self.cnt[*i]==0) as i64;
        }
        for i in self.edge[idx][!f as usize].iter(){
            self.cnt[*i]+=1;
            diff+=(self.cnt[*i]==1) as i64;
        }

        if add<=diff{
            *score+=diff;
            self.out[idx]=!f;

            true
        }
        else{
            for i in self.edge[idx][f as usize].iter(){
                self.cnt[*i]+=1;
            }
            for i in self.edge[idx][!f as usize].iter(){
                self.cnt[*i]-=1;
            }
            false
        }
    }
}


const TL:f64=1.98;


fn sa(r:usize,cur:&mut Out,lim:usize)->bool{
    let mut score=cur.score();

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

    loop{
        if iter&2047==0{
            if get_time()>=TL{break;}

            let p=iter as f64/lim as f64;
            if p>=1.{break;}

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

            let mut id=0;
            while{
                let r=rnd::next();
                th[id]=(heat*((r&4294967295) as f64/4294967296.).ln()) as i64;
                th[id+1]=(heat*((r>>32) as f64/4294967296.).ln()) as i64;
                id+=2;
                id<th.len()
            }{};
        }
        iter+=1;

        if cur.change(th[iter&255],rnd::next()%N,&mut score){
            if score==r as i64{break;}
            up+=1;
        }
    }

    let p=up as f64/iter as f64;
    debug!(r,iter,p);
    debug!(score);
    if cfg!(local){
        assert_eq!(score,cur.score());
    }

    score==r as i64
}


fn solve(input:&In)->[bool;256]{
    let mut out=Out::new();
    let mut ans=out.out;
    let mut best=0;

    let mut pos=1000;
    let mut iter=0;

    while get_time()<=TL{
        iter+=1;
        out.re(input,pos);

        if sa(pos,&mut out,1500000){
            ans=out.out;
            best=pos;
            pos+=4;
        }
        else{
            out.out=ans;
            pos=best+1;
        }
    }

    debug!(iter);
    debug!(best);
    if cfg!(local){
        println!("{best}");
    }

    ans
}


fn main(){
    let input=In::input();
    let mut out=Out::new();
    // out.re(&input,100);
    // eprintln!("{}",out.score());
    let ans=solve(&input);
    
    if !cfg!(local){
        for &i in ans.iter().rev(){
            print!("{}",i as usize);
        }
        println!();
    }
}