#956158 (Rust) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: rhoo
• 提出日時: 2024-02-27 21:03:41
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 952 ms / 1,000 ms
• コード長: 7,500 bytes
• コンパイル時間: 3,247 ms
• コンパイル使用メモリ: 196,396 KB
• 実行使用メモリ: 6,676 KB
• スコア: 86,822,180
• 最終ジャッジ日時: 2024-02-27 21:04:35
• 合計ジャッジ時間: 54,147 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

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

ソースコード

#![allow(non_snake_case)]



// todo: 近傍の種類を増やす


fn main(){
    get_time();
    let mut scan=Scanner::new();
    input!{
        scan,
        n:usize,
        ab:[(i64,i64);n],
    }
    let pos=ab.into_iter().map(|t|P(t.0-MED,t.1-MED)).collect::<Vec<_>>();

    let mut log=[0.;65536];
    for i in 0..65536{
        log[i]=((i as f64+0.5)/65536.).ln();
    }
    rnd::shuffle(&mut log);

    let mut state=State::new(&pos);
    anneal(&mut state,0.2,0.7,&log); // todo
    eprintln!("first_score = {:.2}",state.calc_score());

    let mut tree=Tree::new(&pos,&state.ord);
    anneal(&mut tree,0.95,0.7,&log); // todo
    eprintln!("score = {:.2}",tree.calc_score());

    let ans=tree.restore();
    assert!(ans.len()==M);
    println!("\n{}",ans.len());
    for &(u,v) in &ans{
        println!("{} {}",u+1,v+1);
    }
}



#[derive(Clone)]
struct State<'a>{
    pos:&'a [P],
    ord:Vec<usize>,
    score:f64,
}
impl<'a> State<'a>{
    fn new(pos:&'a [P])->Self{
        let mut ret=Self{
            pos,
            ord:(1..N).collect::<Vec<_>>(),
            score:f64::INFINITY,
        };
        ret.score=ret.calc_score();
        ret
    }

    fn calc_score(&self)->f64{
        let mut p=self.pos[0];
        for &n in &self.ord{
            p=p.merge(self.pos[n]);
        }
        (p.0.abs().max(p.1.abs()) as f64).ln()
    }
}
impl<'a> AnnealState for State<'a>{
    fn score(&self)->f64{
        self.score
    }

    fn trans(&mut self,add:f64)->bool{
        // todo
        let i0=(0..3).map(|_|rnd::get(self.ord.len())).min().unwrap();
        let i1=(0..3).map(|_|rnd::range_skip(0,self.ord.len(),i0)).min().unwrap();
    
        self.ord.swap(i0,i1);
        let new=self.calc_score();
    
        if add>=(new-self.score) as f64{
            self.score=new;
            true
        } else{
            self.ord.swap(i0,i1);
            false
        }
    }
}


const FIX:usize=25; // todo


#[derive(Clone)]
struct Tree{
    fix:P,
    fix_ord:&'static [(usize,usize)],
    is:&'static [usize],
    pos:&'static [P],
    ord:Vec<(usize,usize)>,
    score:f64,
}
impl Tree{
    fn new(pos:&[P],ans:&[usize])->Self{
        let mut fix=P(0,0);
        let mut ord=vec![];
        let mut is=vec![!0;N];
        is[0]=0;
        let mut ps=vec![pos[0]];
        let mut fix_ord=vec![];
        
        for i in 0..ans.len(){
            if ans.len()-i<=FIX{
                fix=fix.merge(pos[ans[i]]);
                fix_ord.push((0,ans[i]));
            } else{
                is[i+1]=ans[i];
                ps.push(pos[ans[i]]);
                ord.push((0,i+1));
            }
        }
        assert!(ps.len()==N-FIX);

        ord.splice(0..0,std::iter::repeat(ord[0]).take(M-FIX-ord.len()));
        assert!(ord.len()+FIX==M);
        
        let mut ret=Tree{
            fix,ord,
            fix_ord:Box::leak(fix_ord.into_boxed_slice()),
            is:Box::leak(is.into_boxed_slice()),
            pos:Box::leak(ps.into_boxed_slice()),
            score:f64::INFINITY,
        };
        ret.score=ret.calc_score();
        ret
    }
    
    fn calc_score(&self)->f64{
        let mut pos:[P;N-FIX]=self.pos.try_into().unwrap();
        for &(u,v) in &self.ord{
            pos[u]=pos[u].merge(pos[v]);
            pos[v]=pos[u];
        }

        let i=(pos[0].0>>FIX)+self.fix.0;
        let j=(pos[0].1>>FIX)+self.fix.1;

        (i.abs().max(j.abs()) as f64).ln()
    }

    fn restore(&self)->Vec<(usize,usize)>{
        self.ord.iter().map(|&t|(self.is[t.0],self.is[t.1]))
            .chain(self.fix_ord.iter().copied())
            .collect()
    }
}
impl AnnealState for Tree{
    fn score(&self)->f64{
        self.score
    }

    fn trans(&mut self,add:f64)->bool{
        let i=(0..3).map(|_|rnd::get(self.ord.len())).min().unwrap();
        let u=if rnd::next()&1==0{ // todo
            0
        } else{
            rnd::get(self.pos.len())
        };
        let v=rnd::range_skip(0,self.pos.len(),u);

        let old=self.ord[i];
        if (u,v)==old || (v,u)==old{
            return false;
        }

        self.ord[i]=(u,v);
        let new=self.calc_score();
        if add>=(new-self.score) as f64{
            self.score=new;
            true
        } else{
            self.ord[i]=old;
            false
        }
    }
}



const N:usize=45;
const M:usize=50;
const MED:i64=5*1e17 as i64;


#[derive(Clone,Copy)]
struct P(i64,i64);
impl P{
    fn merge(self,a:Self)->Self{
        P((self.0+a.0)/2,(self.1+a.1)/2)
    }
}


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

        #[cfg(local)]{
            return (time-START)*1.;
        }
        time-START
    }
}



fn anneal<S:AnnealState>(state:&mut S,tl:f64,init_heat:f64,log:&[f64]){
    let start=get_time();
    let tl=tl-start;
    assert!(0.<tl);

    let mut iter=0;
    let mut heat=0.;

    let mut stay=0;
    let mut best=state.clone();

    while iter&255!=0 || {
        let time=(get_time()-start)/tl;
        heat=init_heat*(1.-time);
        time<=1.
    }{
        iter+=1;
        let add=-heat*log[iter&65535]; // 最小化
        // let add=0.;
        state.trans(add);

        stay+=1;
        if best.score()>state.score(){
            stay=0;
            best=state.clone();
        } else if stay>=1e5 as u64{ // todo
            stay=0;
            *state=best.clone();
        }
    }

    *state=best;
}


trait AnnealState:Clone{
    fn score(&self)->f64;
    fn trans(&mut self,add:f64)->bool;
}




#[allow(unused)]
mod rnd {
    static mut A:u64=1;

    pub fn next()->u32{
        unsafe{
            let mut x=A;
            A*=0xcafef00dd15ea5e5;
            x^=x>>22;
            (x>>22+(x>>61)) as u32
        }
    }

    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 n=range(a,b-1);
        n+(skip<=n) as usize
    }

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



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, $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:ty)=>{
        $scan.read::<$t>()
    };
}