結果

問題 No.5020 Averaging
ユーザー rhoorhoo
提出日時 2024-02-27 18:06:54
言語 Rust
(1.77.0)
結果
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

ソースコード

diff # 

#![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
        }
    })
}
0