#956145 (Rust) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: rhoo
• 提出日時: 2024-02-27 18:06:54
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 953 ms / 1,000 ms
• コード長: 6,318 bytes
• コンパイル時間: 8,222 ms
• コンパイル使用メモリ: 176,176 KB
• 実行使用メモリ: 6,676 KB
• スコア: 82,071,293
• 最終ジャッジ日時: 2024-02-27 18:07:53
• 合計ジャッジ時間: 52,058 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	952 ms; 6,676 KB
testcase_01	AC	951 ms; 6,676 KB
testcase_02	AC	951 ms; 6,676 KB
testcase_03	AC	952 ms; 6,676 KB
testcase_04	AC	952 ms; 6,676 KB
testcase_05	AC	952 ms; 6,676 KB
testcase_06	AC	951 ms; 6,676 KB
testcase_07	AC	951 ms; 6,676 KB
testcase_08	AC	950 ms; 6,676 KB
testcase_09	AC	951 ms; 6,676 KB
testcase_10	AC	951 ms; 6,676 KB
testcase_11	AC	952 ms; 6,676 KB
testcase_12	AC	952 ms; 6,676 KB
testcase_13	AC	951 ms; 6,676 KB
testcase_14	AC	952 ms; 6,676 KB
testcase_15	AC	951 ms; 6,676 KB
testcase_16	AC	952 ms; 6,676 KB
testcase_17	AC	952 ms; 6,676 KB
testcase_18	AC	951 ms; 6,676 KB
testcase_19	AC	952 ms; 6,676 KB
testcase_20	AC	951 ms; 6,676 KB
testcase_21	AC	951 ms; 6,676 KB
testcase_22	AC	951 ms; 6,676 KB
testcase_23	AC	951 ms; 6,676 KB
testcase_24	AC	951 ms; 6,676 KB
testcase_25	AC	951 ms; 6,676 KB
testcase_26	AC	951 ms; 6,676 KB
testcase_27	AC	952 ms; 6,676 KB
testcase_28	AC	952 ms; 6,676 KB
testcase_29	AC	951 ms; 6,676 KB
testcase_30	AC	951 ms; 6,676 KB
testcase_31	AC	951 ms; 6,676 KB
testcase_32	AC	952 ms; 6,676 KB
testcase_33	AC	951 ms; 6,676 KB
testcase_34	AC	952 ms; 6,676 KB
testcase_35	AC	951 ms; 6,676 KB
testcase_36	AC	952 ms; 6,676 KB
testcase_37	AC	952 ms; 6,676 KB
testcase_38	AC	951 ms; 6,676 KB
testcase_39	AC	951 ms; 6,676 KB
testcase_40	AC	951 ms; 6,676 KB
testcase_41	AC	951 ms; 6,676 KB
testcase_42	AC	951 ms; 6,676 KB
testcase_43	AC	951 ms; 6,676 KB
testcase_44	AC	951 ms; 6,676 KB
testcase_45	AC	951 ms; 6,676 KB
testcase_46	AC	953 ms; 6,676 KB
testcase_47	AC	951 ms; 6,676 KB
testcase_48	AC	952 ms; 6,676 KB
testcase_49	AC	952 ms; 6,676 KB

コンパイルメッセージ

warning: constant `M` is never used
   --> Main.rs:129:7
    |
129 | const M:usize=50;
    |       ^
    |
    = note: `#[warn(dead_code)]` on by default

warning: function `multi_start_iter` is never used
   --> Main.rs:288:4
    |
288 | fn multi_start_iter(mut n:usize,tl:f64)->impl Iterator<Item=f64>{
    |    ^^^^^^^^^^^^^^^^

warning: 2 warnings emitted

ソースコード

#![allow(non_snake_case)]



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,t.1)).collect::<Vec<_>>();
    let mut state=State::new();
    anneal(&pos,&mut state,0.95);

    state.score(&pos,true);

    assert!(state.ord.len()==N-1); // todo: サイズNに限定している
    println!("\n{}",state.ord.len());
    for i in 0..state.ord.len(){
        println!("1 {}",state.ord[i]+1);
    }
}



#[derive(Clone)]
struct State{
    ord:Vec<usize>, // 状態を限定しない
    score:f64,
}
impl State{
    fn new()->State{
        State{
            ord:(1..N).collect::<Vec<_>>(),
            score:f64::INFINITY,
        }
    }

    fn score(&self,pos:&[P],dbg:bool)->f64{
        let mut p=pos[0];
        for &n in &self.ord{
            p=p.merge(pos[n]);
        }
        if dbg{
            eprintln!("# pos = {:?}",(p.0,p.1));
            eprintln!("score = {:.2}",(p.cost() as f64).log10());
        }
        (p.cost() as f64).ln()
    }
}


fn trans(pos:&[P],state:&mut State,add:f64)->bool{
    // スコアの最小化ならadd>=diffで更新
    let i0=rnd::get(state.ord.len());
    let i1=rnd::range_skip(0,state.ord.len(),i0);
    let i2=if rnd::get(20)==0{
        rnd::range_skip(0,state.ord.len(),i0)
    } else{
        i1
    };

    state.ord.swap(i0,i1);
    state.ord.swap(i1,i2);
    let new=state.score(pos,false);

    if add>=(new-state.score) as f64{
        state.score=new;
        true
    } else{
        state.ord.swap(i1,i2);
        state.ord.swap(i0,i1);
        false
    }
}


fn anneal(pos:&[P],state:&mut State,tl:f64){
    let mut log=[0.;65536];
    for i in 0..65536{
        log[i]=((i as f64+0.5)/65536.).ln();
    }
    rnd::shuffle(&mut log);

    let start=get_time();
    let tl=tl-start;
    assert!(0.<tl);

    let mut valid=0;
    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;
        const H:(f64,f64)=(0.7,0.);
        heat=H.0+(H.1-H.0)*time;
        time<=1.
    }{
        iter+=1;
        let add=-heat*log[iter&65535]; // 最小化
        // let add=0.;
        valid+=trans(pos,state,add) as usize;

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

    eprintln!("iter = {}",iter);
    eprintln!("ratio = {:.3}",valid as f64/iter as f64);

    *state=best;
}



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 cost(self)->i64{
        (self.0-MED).abs().max((self.1-MED).abs())
    }
}


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
    }
}



#[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 next64()->u64{
        (next() as u64)<<32|next() as u64
    }

    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 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));
        }
    }

    pub fn shuffle_iter<T:Copy>(list:&mut [T])->impl Iterator<Item=T>+'_{
        (0..list.len()).rev().map(|i|{list.swap(i,get(i+1));list[i]})
    }
}


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>()
    };
}



fn multi_start_iter(mut n:usize,tl:f64)->impl Iterator<Item=f64>{
    std::iter::from_fn(move||{
        if n==0{
            None
        } else{
            let time=get_time();
            let ret=Some((tl-time)/n as f64+time);
            n-=1;
            ret
        }
    })
}