結果

問題 No.5005 3-SAT
ユーザー rhoorhoo
提出日時 2022-06-26 11:58:54
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,984 ms / 2,000 ms
コード長 6,997 bytes
コンパイル時間 1,313 ms
実行使用メモリ 6,952 KB
スコア 615
最終ジャッジ日時 2022-06-26 12:02:24
合計ジャッジ時間 208,050 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,983 ms
3,272 KB
testcase_01 AC 1,983 ms
3,260 KB
testcase_02 AC 1,983 ms
3,164 KB
testcase_03 AC 1,982 ms
3,112 KB
testcase_04 AC 1,984 ms
3,204 KB
testcase_05 AC 1,983 ms
3,132 KB
testcase_06 AC 1,984 ms
3,132 KB
testcase_07 AC 1,984 ms
3,248 KB
testcase_08 AC 1,983 ms
3,196 KB
testcase_09 AC 1,982 ms
3,356 KB
testcase_10 AC 1,984 ms
3,272 KB
testcase_11 AC 1,983 ms
3,208 KB
testcase_12 AC 1,984 ms
3,176 KB
testcase_13 AC 1,984 ms
3,244 KB
testcase_14 AC 1,982 ms
3,172 KB
testcase_15 AC 1,983 ms
3,124 KB
testcase_16 AC 1,983 ms
3,200 KB
testcase_17 AC 1,983 ms
3,180 KB
testcase_18 AC 1,984 ms
3,180 KB
testcase_19 AC 1,983 ms
3,044 KB
testcase_20 AC 1,982 ms
3,268 KB
testcase_21 AC 1,983 ms
3,148 KB
testcase_22 AC 1,983 ms
3,212 KB
testcase_23 AC 1,984 ms
3,152 KB
testcase_24 AC 1,983 ms
3,232 KB
testcase_25 AC 1,982 ms
3,176 KB
testcase_26 AC 1,983 ms
3,248 KB
testcase_27 AC 1,983 ms
3,116 KB
testcase_28 AC 1,983 ms
3,248 KB
testcase_29 AC 1,983 ms
3,116 KB
testcase_30 AC 1,983 ms
3,248 KB
testcase_31 AC 1,982 ms
3,248 KB
testcase_32 AC 1,984 ms
3,240 KB
testcase_33 AC 1,983 ms
3,112 KB
testcase_34 AC 1,983 ms
3,112 KB
testcase_35 AC 1,982 ms
3,144 KB
testcase_36 AC 1,982 ms
3,208 KB
testcase_37 AC 1,984 ms
3,248 KB
testcase_38 AC 1,983 ms
3,120 KB
testcase_39 AC 1,983 ms
3,260 KB
testcase_40 AC 1,983 ms
5,160 KB
testcase_41 AC 1,982 ms
5,456 KB
testcase_42 AC 1,982 ms
4,904 KB
testcase_43 AC 1,983 ms
5,156 KB
testcase_44 AC 1,983 ms
4,904 KB
testcase_45 AC 1,983 ms
4,904 KB
testcase_46 AC 1,982 ms
4,900 KB
testcase_47 AC 1,982 ms
4,904 KB
testcase_48 AC 1,983 ms
4,904 KB
testcase_49 AC 1,983 ms
4,900 KB
testcase_50 AC 1,984 ms
4,900 KB
testcase_51 AC 1,983 ms
4,904 KB
testcase_52 AC 1,984 ms
4,900 KB
testcase_53 AC 1,982 ms
3,268 KB
testcase_54 AC 1,983 ms
5,160 KB
testcase_55 AC 1,984 ms
5,156 KB
testcase_56 AC 1,983 ms
4,904 KB
testcase_57 AC 1,982 ms
4,900 KB
testcase_58 AC 1,983 ms
4,900 KB
testcase_59 AC 1,983 ms
5,156 KB
testcase_60 AC 1,983 ms
5,160 KB
testcase_61 AC 1,983 ms
4,904 KB
testcase_62 AC 1,983 ms
5,156 KB
testcase_63 AC 1,983 ms
4,904 KB
testcase_64 AC 1,982 ms
4,904 KB
testcase_65 AC 1,983 ms
4,900 KB
testcase_66 AC 1,983 ms
4,900 KB
testcase_67 AC 1,984 ms
4,904 KB
testcase_68 AC 1,982 ms
4,900 KB
testcase_69 AC 1,983 ms
4,904 KB
testcase_70 AC 1,983 ms
4,904 KB
testcase_71 AC 1,984 ms
4,900 KB
testcase_72 AC 1,983 ms
4,904 KB
testcase_73 AC 1,982 ms
4,904 KB
testcase_74 AC 1,984 ms
4,900 KB
testcase_75 AC 1,983 ms
4,904 KB
testcase_76 AC 1,984 ms
6,952 KB
testcase_77 AC 1,983 ms
4,900 KB
testcase_78 AC 1,984 ms
4,904 KB
testcase_79 AC 1,983 ms
6,948 KB
testcase_80 AC 1,983 ms
6,948 KB
testcase_81 AC 1,983 ms
4,900 KB
testcase_82 AC 1,983 ms
6,952 KB
testcase_83 AC 1,984 ms
6,948 KB
testcase_84 AC 1,982 ms
4,904 KB
testcase_85 AC 1,984 ms
4,900 KB
testcase_86 AC 1,982 ms
4,900 KB
testcase_87 AC 1,983 ms
6,948 KB
testcase_88 AC 1,983 ms
4,900 KB
testcase_89 AC 1,983 ms
4,904 KB
testcase_90 AC 1,983 ms
4,904 KB
testcase_91 AC 1,983 ms
6,948 KB
testcase_92 AC 1,983 ms
6,948 KB
testcase_93 AC 1,983 ms
4,904 KB
testcase_94 AC 1,983 ms
4,900 KB
testcase_95 AC 1,982 ms
4,904 KB
testcase_96 AC 1,983 ms
4,900 KB
testcase_97 AC 1,983 ms
4,908 KB
testcase_98 AC 1,983 ms
4,904 KB
testcase_99 AC 1,983 ms
4,900 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `p`
   --> Main.rs:265:9
    |
265 |     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: field is never read: `edge2`
   --> Main.rs:108:5
    |
108 |     edge2:[[(usize,bool);3];M]
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 2 warnings emitted

ソースコード

diff # 

#[allow(unused)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes.by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

#[allow(unused)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

    ($next:expr, $t:ty) => {
        $next().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{
    edge1:[[Vec<usize>;2];N],
    edge2:[[(usize,bool);3];M]
}
impl In{
    fn input()->In{
        input!{
            q:[([usize;3],[usize;3]);M]
        }

        let mut edge2=[[(0,false);3];M];
        for (i,v) in q.iter().enumerate(){
            for (j,(id,f)) in v.0.iter().zip(v.1.iter()).enumerate(){
                edge2[i][j]=(*id,*f==1);
            }
        }

        let mut edge1=[();N].map(|_|[vec![],vec![]]);
        for i in 0..M{
            for (idx,f) in edge2[i].iter(){
                edge1[*idx][*f as usize].push(i);
            }
        }

        In{edge1,edge2}
    }
}


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.edge1[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,new:&[(usize,bool)],score:&mut i64)->bool{
        let mut diff=0;
        for &(idx,f) in new{
            if self.out[idx]!=f{
                for i in self.edge[idx][!f as usize].iter(){
                    self.cnt[*i]-=1;
                    if self.cnt[*i]==0{
                        diff-=1;
                    }
                }
                for i in self.edge[idx][f as usize].iter(){
                    self.cnt[*i]+=1;
                    if self.cnt[*i]==1{
                        diff+=1;
                    }
                }
            }
        }

        if add<=diff{
            *score+=diff;
            for &(idx,f) in new{
                self.out[idx]=f;
            }

            true
        }
        else{
            for &(idx,f) in new{
                if self.out[idx]!=f{
                    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)->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;}

            const LIM:f64=500000.;
            let p=iter as f64/LIM as f64;
            if p>=1.{break;}

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

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

        let rnd=rnd::next();

        if cur.change(th[iter&255],&[(rnd%N,rnd>>63==0)],&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){
        if score==r as i64{
            eprintln!("success");
        }
        else{
            eprintln!("failed");
        }
    }

    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=950;
    let mut range=16;

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

        if sa(pos,&mut out){
            ans=out.out;
            best=pos;
            pos+=range;
        }
        else{
            out.out=ans;
            range=1.max(range>>1);
            pos-=range;
            pos=(pos-range).max(best+1);
        }
    }

    eprintln!("score: {}",best);
    if cfg!(local){
        println!("{best}");
    }

    ans
}


fn main(){
    let input=In::input();
    let ans=solve(&input);
    
    if !cfg!(local){
        for &i in ans.iter(){
            print!("{}",i as usize);
        }
        println!();
    }
}
0