#938563 (Rust) No.2596 Christmas Eve (Heuristic ver.)

• 問題: No.2596 Christmas Eve (Heuristic ver.)
• ユーザー: rhoo
• 提出日時: 2023-12-16 00:41:46
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 1,203 ms / 1,224 ms
• コード長: 19,379 bytes
• コンパイル時間: 2,202 ms
• コンパイル使用メモリ: 202,972 KB
• 実行使用メモリ: 6,676 KB
• スコア: 4,999,033
• 最終ジャッジ日時: 2023-12-23 20:38:16
• 合計ジャッジ時間: 163,937 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

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

コンパイルメッセージ

warning: methods `clear`, `is_empty`, and `len` are never used
   --> Main.rs:720:8
    |
706 | impl<T:Ord+Copy> HeapMap<T>{
    | --------------------------- methods in this implementation
...
720 |     fn clear(&mut self){
    |        ^^^^^
...
743 |     fn is_empty(&self)->bool{
    |        ^^^^^^^^
...
747 |     fn len(&self)->usize{
    |        ^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: methods `len` and `fill` are never used
   --> Main.rs:824:8
    |
781 | impl IndexSet{
    | ------------- methods in this implementation
...
824 |     fn len(&self)->usize{
    |        ^^^
...
832 |     fn fill(&mut self){
    |        ^^^^

warning: 2 warnings emitted

ソースコード

#![allow(non_snake_case)]


fn main(){
    get_time();
    set_phase(0);
    
    let input=Input::new();
    let state=State::new(&input);
    
    let mut sa=SA::new(state);

    sa.solve(&input,0.8);
    set_phase(1);

    let mut best=sa.state.clone();
    let mut range=best.get_range(&input);

    while get_time()<=1.2{
        sa.state=best.clone();
        sa.state.reset(&input,(range.0,range.1-1));
        sa.solve(&input,1.2);

        if sa.state.cand.is_empty(){
            best=sa.state.clone();
            range=best.get_range(&input);
        }
    }
    
    eprintln!("score = {}",range.1-range.0);

    for &[a,b,c,d] in &best.tree{
        println!("{} {} {} {}",c%N+1,a+1,b+1,d%N+1);
    }
}



static mut PHASE:u8=0;
fn set_phase(a:u8){
    unsafe{PHASE=a;}
}
fn phase()->u8{
    unsafe{PHASE}
}


use std::cmp::Reverse;


#[derive(Clone)]
struct State{
    tree:Vec<[usize;4]>,
    pos:[usize;4*N],
    min:HeapMap<Reverse<i64>>,
    max:HeapMap<i64>,
    range:(i64,i64),
    cand:IndexSet,
}
impl State{
    fn new(input:&Input)->State{
        let mut is:Vec<_>=(0..4*N).collect();
        fn find(input:&Input,is:&mut Vec<usize>,mut f:impl FnMut(usize)->bool)->usize{
            let idx=(0..is.len()).filter(|&i|f(is[i])).min_by_key(|&i|input.W[is[i]]).unwrap();
            is.swap_remove(idx)
        }
        
        let mut tree=vec![];
        let mut pos=[!0;4*N];
        let mut min=HeapMap::new(input.K);
        let mut max=HeapMap::new(input.K);
        
        for i in 0..input.K{
            let a=find(&input,&mut is,|t|(3*N..).contains(&t));
            let b=find(&input,&mut is,|t|(2*N..3*N).contains(&t) && input.W[t]>input.W[a]);
            let c=find(&input,&mut is,|t|(..2*N).contains(&t) && input.W[t]>input.W[b]);
            let d=find(&input,&mut is,|t|(..2*N).contains(&t) && input.W[t]>input.W[b]);

            let new=[d,c,b,a];
            tree.push(new);

            let mut h=0;
            for &n in &new{
                pos[n]=i;
                h+=input.H[n];
            }

            min.insert(i,Reverse(h));
            max.insert(i,h);
        }

        let cand=IndexSet::new(input.K);

        State{tree,pos,min,max,range:(0,0),cand}
    }

    fn get_height(&self,input:&Input,n:usize)->i64{
        self.tree[n].iter().map(|&i|input.H[i]).sum()
    }

    fn change(&mut self,n:usize,h:i64){
        if phase()==0{
            self.min.change(n,Reverse(h));
            self.max.change(n,h);
        }
    }

    fn is_valid(&self,input:&Input,n:usize)->bool{
        let [a,b,c,d]=self.tree[n];
        input.W[a]>input.W[c] && input.W[b]>input.W[c] && input.W[c]>input.W[d]
    }

    fn get_diff(&self,input:&Input,n:usize)->i64{
        assert!(phase()==1);
        let h=self.get_height(input,n);
        
        if h<self.range.0{
            self.range.0-h
        } else if self.range.1<h{
            h-self.range.1
        } else{
            0
        }
    }
    
    fn score(&self,input:&Input)->i64{
        if phase()==0{
            let min=self.min.peek().unwrap().1.0;
            let max=self.max.peek().unwrap().1;
    
            max-min
        } else{
            (0..input.K).map(|i|self.get_diff(input,i)).sum()
        }
    }

    fn get_range(&self,input:&Input)->(i64,i64){
        assert!(phase()==1);
        let min=(0..input.K).map(|i|self.get_height(input,i)).min().unwrap();
        let max=(0..input.K).map(|i|self.get_height(input,i)).max().unwrap();
        (min,max)
    }

    fn reset(&mut self,input:&Input,range:(i64,i64)){
        assert!(phase()==1);
        self.range=range;
        self.cand.clear();
        for i in 0..input.K{
            if self.get_diff(input,i)>0{
                self.cand.add(i);
            }
        }
    }
}


fn trans(input:&Input,state:&mut State,add:f64,score:&mut i64)->bool{
    // スコアの最大化ならadd<=diffで更新
    let (i0,min,max);
    if phase()==1{
        i0=state.cand.rand();
        (min,max)=(0,0);
    } else if rnd::next()&1==0{
        i0=state.max.peek().unwrap().0;
        min=state.min.peek().unwrap().1.0;
        max=state.max.peek2().unwrap().1;
    } else{
        i0=state.min.peek().unwrap().0;
        min=state.min.peek2().unwrap().1.0;
        max=state.max.peek().unwrap().1;
    };
    let a0=rnd::get(4);

    let n0=state.tree[i0][a0];
    let n1=if a0<2{
        rnd::range_skip(0,2*N,n0)
    } else if a0==2{
        rnd::range_skip(2*N,3*N,n0)
    } else{
        rnd::range_skip(3*N,4*N,n0)
    };

    if state.pos[n1]==!0{
        let mut new_score;
        if phase()==0{
            state.tree[i0][a0]=n1;
            if !state.is_valid(input,i0){
                state.tree[i0][a0]=n0;
                return false;
            }

            let h0=state.get_height(input,i0);
            new_score=max.max(h0)-min.min(h0);
        } else{
            new_score=*score-state.get_diff(input,i0);

            state.tree[i0][a0]=n1;
            if !state.is_valid(input,i0){
                state.tree[i0][a0]=n0;
                return false;
            }
            
            new_score+=state.get_diff(input,i0);
        }

        if (new_score-*score) as f64<=add{
            state.change(i0,state.get_height(input,i0));
            if phase()==0{
                *score=state.score(input);
            } else{
                *score=new_score;
            }
            state.pos[n0]=!0;
            state.pos[n1]=i0;

            if phase()==1 && state.get_diff(input,i0)==0{
                state.cand.del(i0);
            }

            true
        } else{
            state.tree[i0][a0]=n0;
            
            false
        }
    } else{
        let i1=state.pos[n1];
        let a1=(0..4).find(|&a|state.tree[i1][a]==n1).unwrap();

        let mut new_score;
        if phase()==0{
            state.tree[i0][a0]=n1;
            state.tree[i1][a1]=n0;
    
            if !state.is_valid(input,i0) || !state.is_valid(input,i1){
                state.tree[i0][a0]=n0;
                state.tree[i1][a1]=n1;
                return false;
            }
            
            let h0=state.get_height(input,i0);
            let h1=state.get_height(input,i1);
            new_score=max.max(h0).max(h1)-min.min(h0).min(h1);
        } else{
            new_score=*score-state.get_diff(input,i0)-state.get_diff(input,i1);

            state.tree[i0][a0]=n1;
            state.tree[i1][a1]=n0;
            if !state.is_valid(input,i0) || !state.is_valid(input,i1){
                state.tree[i0][a0]=n0;
                state.tree[i1][a1]=n1;
                return false;
            }
            
            new_score+=state.get_diff(input,i0)+state.get_diff(input,i1);
        }
        
        if (new_score-*score) as f64<=add{
            state.change(i0,state.get_height(input,i0));
            state.change(i1,state.get_height(input,i1));

            if phase()==0{
                *score=state.score(input);
            } else{
                *score=new_score;
            }

            state.pos[n0]=i1;
            state.pos[n1]=i0;

            if phase()==1{
                let d0=state.get_diff(input,i0);
                let d1=state.get_diff(input,i1);

                if d0==0{
                    state.cand.del(i0);
                }
                if d1==0 && state.cand.contains(i1){
                    state.cand.del(i1);
                } else if d1!=0 && !state.cand.contains(i1){
                    state.cand.add(i1);
                }
            }

            true
        } else{
            state.tree[i0][a0]=n0;
            state.tree[i1][a1]=n1;
            
            false
        }
    }
}



////////////////////////////////////////////  ここからライブラリと入力 ////////////////////////////////////////////



struct SA{
    start:f64,
    tl:f64,
    time:f64,
    heat:f64,
    table:[f64;65536],
    state:State,
}
impl SA{
    fn new(state:State)->SA{
        let mut table=[0.;65536];
        for i in 0..65536{
            table[i]=((i as f64+0.5)/65536.).ln();
        }
        rnd::shuffle(&mut table);

        SA{
            start:0.,
            tl:0.,
            time:0.,
            heat:0.,
            table,
            state,
        }
    }
    
    fn update(&mut self)->bool{
        self.time=(get_time()-self.start)/self.tl;
        if self.time>=1.{
            return false;
        }

        // todo
        if phase()==0{
            const T0:f64=6.;
            const T1:f64=1.;
            self.heat=T0*(T1/T0).powf(self.time.powf(1.5));
        } else{
            const T0:f64=5.;
            const T1:f64=1.;
            self.heat=T0*(T1/T0).powf(self.time.powf(1.5));
        }

        true
    }
    
    fn solve(&mut self,input:&Input,tl:f64){
        self.start=get_time();
        assert!(self.start<tl);
        self.tl=tl-self.start;
        
        let mut score=self.state.score(input);
        let mut best_score=score;
        let mut best=self.state.clone();
        let mut iter=0;

        while iter&255!=0 || self.update(){
            iter+=1;
            let add=-self.heat*self.table[iter&65535]; // 最大化
            
            trans(input,&mut self.state,add,&mut score);

            if 0.1<self.time && best_score>score{
                best_score=score;
                best=self.state.clone();
            }

            if phase()==1 && score==0{
                return;
            }
        }

        assert!(self.state.score(input)==score);
        self.state=best;
    }
}



const N:usize=500;

struct Input{
    K:usize,
    H:Vec<i64>,
    W:Vec<i64>,
}
impl Input{
    fn new()->Input{
        let mut scan=Scanner::new();
        input!{
            scan,
            n:usize,
            K:usize,
            a:[i64;n],
            b:[i64;n],
            c:[i64;2*n],
            d:[i64;2*n],
            e:[i64;n],
            f:[i64;n],
        }
        assert!(n==N);

        Input{
            K,
            H:d.into_iter().chain(b).chain(f).collect(),
            W:c.into_iter().chain(a).chain(e).collect(),
        }
    }
}



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

        #[cfg(local)]{
            (time-START)*1.4
        }
        #[cfg(not(local))]{
            time-START
        }
    }
}


#[macro_export]
macro_rules! timer{
    ()=>{
        #[cfg(local)]
        let _timer=Timer(get_time());
    }
}

static mut TIME:f64=0.;
struct Timer(f64);
impl Drop for Timer{
    fn drop(&mut self){
        unsafe{
            TIME+=get_time()-self.0
        }
    }
}


#[allow(unused)]
mod rnd {
    const C:u64=0xcafef00dd15ea5e5;
    static mut N:u64=C;

    pub fn set_seed(seed:u64){
        unsafe{
            N^=seed<<1;
        }
    }
    
    pub fn next()->u32{
        unsafe{
            let mut x=N;
            x^=x>>22;
            N*=C;
            (x>>22+(x>>61)) as u32
        }
    }

    pub fn hash()->u64{
        unsafe{
            let x=N;
            N*=C;
            x
        }
    }

    pub fn nextf()->f64{
        unsafe{
            std::mem::transmute::<u64,f64>(0x3ff0000000000000|(next() as u64)<<20)-1.
        }
    }

    pub fn get(n:usize)->usize{
        assert!(n<=u32::MAX as usize);
        next() as usize*n>>32
    }

    pub fn range(a:usize,b:usize)->usize{
        assert!(a<b);
        get(b-a)+a
    }

    pub fn range_skip(a:usize,b:usize,skip:usize)->usize{
        assert!(a<=skip && skip<b);
        let ret=range(a,b-1);
        ret+(skip<=ret) as usize
    }

    pub fn rangei(a:i64,b:i64)->i64{
        assert!(a<b);
        get((b-a) as usize) as i64+a
    }

    pub fn shuffle<T>(list:&mut [T]){
        for i in (0..list.len()).rev(){
            list.swap(i,get(i+1));
        }
    }
}


trait RandomChoice{
    type Output;
    fn choice(&self)->Self::Output;
}
impl<T:Copy> RandomChoice for [T]{
    type Output=T;
    fn choice(&self)->T{
        self[rnd::get(self.len())]
    }
}



struct Scanner{
    stack:std::str::SplitAsciiWhitespace<'static>
}
impl Scanner{
    fn new()->Self{
        use std::io::Read;
        let mut tmp=String::new();
        std::io::stdin().read_to_string(&mut tmp).unwrap();
        Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}
    }

    fn read<T:std::str::FromStr>(&mut self)->T{
        self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))
    }
}


#[macro_export]
macro_rules! input{
    ($scan:expr $(,)?)=>{};
    ($scan:expr, mut $name:ident:$t:tt $($rest:tt)*)=>{
        let mut $name=read_value!($scan,$t);
        input!{$scan $($rest)*}
    };
    ($scan:expr, $name:ident:$t:tt $($rest:tt)*)=>{
        let $name=read_value!($scan,$t);
        input!{$scan $($rest)*}
    };
}

#[macro_export]
macro_rules! read_value{
    ($scan:expr, ($($t:tt),*))=>{
        ($(read_value!($scan, $t)),*)
    };
    ($scan:expr, [$t:tt;$len:expr])=>{
        (0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
    };
    ($scan:expr, [$t:tt])=>{
        (0..$scan.read()).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
    };
    ($scan:expr, Chars)=>{
        read_value!($scan,String).chars().collect::<Vec<char>>()
    };
    ($scan:expr, Usize1)=>{
        read_value!($scan,usize)-1
    };
    ($scan:expr, $t:ty)=>{
        $scan.read::<$t>()
    };
}





trait RecordSwap<T>{
    fn start(&mut self,t:T,n:usize);
    fn next(&mut self,t:T,n:usize);
    fn finish(&mut self);
}

struct NopRecorder();
impl<T> RecordSwap<T> for NopRecorder{
    fn start(&mut self,_:T,_:usize){}
    fn next(&mut self,_:T,_:usize){}
    fn finish(&mut self){}
}


use std::cmp::Ordering::{self,*};

fn sift_up<T:Copy,const START:bool>(slice:&mut [T],mut pos:usize,mut f:impl FnMut(&T,&T)->Ordering,record:&mut impl RecordSwap<T>){
    let target=slice[pos];
    if START{
        record.start(target,pos);
    }
    while 0<pos{
        let next=(pos-1)/2;
        if f(&target,&slice[next])!=Greater{
            break;
        }
        slice[pos]=slice[next];
        pos=next;
        record.next(slice[pos],pos);
    }
    slice[pos]=target;
    record.finish();
}


fn sift_down<T:Copy>(slice:&mut [T],mut pos:usize,mut f:impl FnMut(&T,&T)->Ordering,record:&mut impl RecordSwap<T>){
    let target=slice[pos];
    let mut next=pos*2+1;
    record.start(target,pos);
    let limit=slice.len().saturating_sub(1);
    while next<limit{
        next+=(f(&slice[next],&slice[next+1])!=Greater) as usize;
        if f(&slice[next],&target)!=Greater{
            break;
        }
        slice[pos]=slice[next];
        pos=next;
        record.next(slice[pos],pos);
        next=2*pos+1;
    }

    if next==slice.len()-1 && f(&slice[next],&target)==Greater{
        slice[pos]=slice[next];
        pos=next;
        record.next(slice[pos],pos);
    }
    slice[pos]=target;
    record.finish();
}

fn sift_update<T:Copy>(slice:&mut [T],pos:usize,mut f:impl FnMut(&T,&T)->Ordering,record:&mut impl RecordSwap<T>){
    let parent=(pos-1)/2;
    if 0<pos && f(&slice[pos],&slice[parent])==Greater{
        record.start(slice[pos],pos);
        record.next(slice[parent],parent);
        slice.swap(pos,parent);
        sift_up::<_,false>(slice,parent,f,record);
    } else{
        sift_down(slice,pos,f,record);
    }
}

fn peek2_pos<T>(slice:&[T],mut f:impl FnMut(&T,&T)->Ordering)->Option<usize>{
    if slice.len()<=1{
        None
    } else if slice.len()==2{
        Some(1)
    }else{
        Some(1+(f(&slice[2],&slice[1])==Greater) as usize)
    }
}

fn peek2<T>(slice:&[T],f:impl FnMut(&T,&T)->Ordering)->Option<&T>{
    peek2_pos(slice,f).map(|t|&slice[t])
}





struct HeapMapRecorder<'a>{
    idx:&'a mut [usize],
    start:usize,
    prev:usize,
}
impl<'a> HeapMapRecorder<'a>{
    fn new(idx:&'a mut [usize])->Self{
        Self{idx,start:!0,prev:!0}
    }
}
impl<'a,T:Copy> RecordSwap<(usize,T)> for HeapMapRecorder<'a>{
    fn start(&mut self,t:(usize,T),n:usize){
        self.start=t.0;
        self.prev=n;
    }

    fn next(&mut self,t:(usize,T),n:usize){
        self.idx[t.0]=self.prev;
        self.prev=n;
    }

    fn finish(&mut self){
        self.idx[self.start]=self.prev;
    }
}


#[derive(Clone)]
struct HeapMap<T:Ord>{
    heap:Vec<(usize,T)>,
    idx:Vec<usize>,
    len:usize,
}
impl<T:Ord+Copy> HeapMap<T>{
    fn new(n:usize)->Self{
        let mut heap:Vec<(usize,T)>=Vec::with_capacity(n);
        unsafe{heap.set_len(n);}
        for i in 0..n{
            heap[i].0=i;
        }
        HeapMap{
            heap,
            idx:(0..n).collect(),
            len:0,
        }
    }

    fn clear(&mut self){
        self.len=0;
    }

    fn insert(&mut self,n:usize,t:T){
        let pos=self.idx[n];
        assert!(self.len<=pos);
        self.heap[pos].1=t;
        self.heap.swap(self.len,pos);
        self.idx.swap(n,self.heap[pos].0);
        
        sift_up::<_,true>(&mut self.heap[..=self.len],self.len,|a,b|a.1.cmp(&b.1),&mut HeapMapRecorder::new(&mut self.idx));
        self.len+=1;
    }

    fn change(&mut self,n:usize,new:T){
        let pos=self.idx[n];
        assert!(pos<self.len);
        assert!(self.heap[pos].0==n);
        self.heap[pos].1=new;
        sift_update(&mut self.heap[..self.len],pos,|a,b|a.1.cmp(&b.1),&mut HeapMapRecorder::new(&mut self.idx));
    }

    fn is_empty(&self)->bool{
        self.len==0
    }

    fn len(&self)->usize{
        self.len
    }

    fn contains(&self,n:usize)->bool{
        self.idx[n]<self.len
    }

    fn peek(&self)->Option<(usize,T)>{
        self.heap[..self.len].get(0).copied()
    }

    fn peek2(&self)->Option<(usize,T)>{
        peek2(&self.heap[..self.len],|a,b|a.1.cmp(&b.1)).copied()
    }
}
impl<T:Ord+Copy> std::ops::Index<usize> for HeapMap<T>{
    type Output=T;
    fn index(&self,n:usize)->&T{
        assert!(self.contains(n));
        &self.heap[self.idx[n]].1
    }
}





#[derive(Clone)]
struct IndexSet{
    pos:Vec<usize>,
    que:Vec<usize>,
    len:usize
}
impl IndexSet{
    fn new(n:usize)->Self{
        IndexSet{
            pos:(0..n).collect(),
            que:(0..n).collect(),
            len:0
        }
    }

    fn add(&mut self,a:usize){
        let p=self.pos[a];
        assert!(self.len<=p);

        self.que.swap(p,self.len);
        self.pos.swap(a,self.que[p]);
        self.len+=1;
    }

    fn del(&mut self,a:usize){
        let p=self.pos[a];
        assert!(p<self.len);

        self.que.swap(p,self.len-1);
        self.pos.swap(a,self.que[p]);
        self.len-=1;
    }

    fn rand(&self)->usize{
        self.que[rnd::get(self.len)]
    }

    fn to_slice(&self)->&[usize]{
        &self.que[..self.len]
    }

    fn contains(&self,v:usize)->bool{
        self.pos[v]<self.len
    }

    fn is_empty(&self)->bool{
        self.len==0
    }

    fn len(&self)->usize{
        self.len
    }

    fn clear(&mut self){
        self.len=0;
    }

    fn fill(&mut self){
        self.len=self.pos.len();
    }
}

impl std::cmp::PartialEq for IndexSet{
    fn eq(&self,a:&IndexSet)->bool{
        self.pos.len()==a.pos.len() && self.len==a.len
        && self.to_slice().iter().all(|&n|a.contains(n))
    }
}