#783102 (Rust) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: rhoo
• 提出日時: 2022-07-30 16:24:40
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 982 ms / 1,000 ms
• コード長: 9,520 bytes
• コンパイル時間: 1,081 ms
• 実行使用メモリ: 6,952 KB
• スコア: 8,166,259
• 最終ジャッジ日時: 2022-07-30 16:25:36
• 合計ジャッジ時間: 33,144 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	982 ms; 4,904 KB
testcase_01	AC	981 ms; 6,952 KB
testcase_02	AC	981 ms; 4,900 KB
testcase_03	AC	982 ms; 4,900 KB
testcase_04	AC	982 ms; 6,948 KB
testcase_05	AC	982 ms; 6,952 KB
testcase_06	AC	982 ms; 4,904 KB
testcase_07	AC	981 ms; 4,908 KB
testcase_08	AC	982 ms; 4,900 KB
testcase_09	AC	982 ms; 6,948 KB
testcase_10	AC	981 ms; 6,948 KB
testcase_11	AC	982 ms; 4,904 KB
testcase_12	AC	982 ms; 4,904 KB
testcase_13	AC	981 ms; 4,904 KB
testcase_14	AC	982 ms; 6,948 KB
testcase_15	AC	982 ms; 4,904 KB
testcase_16	AC	982 ms; 4,904 KB
testcase_17	AC	982 ms; 4,904 KB
testcase_18	AC	981 ms; 6,952 KB
testcase_19	AC	982 ms; 4,904 KB
testcase_20	AC	982 ms; 4,904 KB
testcase_21	AC	982 ms; 4,904 KB
testcase_22	AC	982 ms; 6,948 KB
testcase_23	AC	982 ms; 4,904 KB
testcase_24	AC	982 ms; 4,900 KB
testcase_25	AC	981 ms; 6,952 KB
testcase_26	AC	982 ms; 4,904 KB
testcase_27	AC	982 ms; 4,900 KB
testcase_28	AC	982 ms; 4,904 KB
testcase_29	AC	981 ms; 4,904 KB

コンパイルメッセージ

warning: unused variable: `p`
   --> Main.rs:365:9
    |
365 |     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: unused variable: `p`
   --> Main.rs:418:9
    |
418 |     let p=up as f64/iter as f64;
    |         ^ help: if this is intentional, prefix it with an underscore: `_p`

warning: 2 warnings emitted

ソースコード

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}



#[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{
    ()=>{
        eprintln!();
    };
    ($x:literal)=>{
        eprintln!("{:?}",$x);
    };
    ($x:expr)=>{
        eprintln!("{}: {:?}",stringify!($x),$x);
    };
    ($x:literal,$($l:expr),*)=>{
        eprint!("{:?}, ",$x);
        debug!($($l),*);
    };
    ($x:expr,$($l:expr),*)=>{
        eprint!("{}: {:?}, ",stringify!($x),$x);
        debug!($($l),*);
    }
}
#[cfg(not(local))]
#[allow(unused)]
macro_rules! debug{
    ($($_:expr),*)=>{}
}

#[allow(unused)]
mod rnd {
    static mut S:usize=88172645463325252;
    #[inline]
    pub fn next()->usize{
        unsafe{
            S^=S<<7;
            S^=S>>9;
            S
        }
    }
    
    #[inline]
    pub fn nextf()->f64{
        unsafe{
            std::mem::transmute::<_,f64>(0x3ff0000000000000|next()&0xfffffffffffff)-1.
        }
    }

    // [a,b)
    #[inline]
    pub fn range(a:usize,b:usize)->usize{
        next()%(b-a)+a
    }

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

    #[inline]
    pub fn exu(a:usize,b:usize,skip:usize)->usize{
        let ret=range(a,b-1);
        if ret==skip{b-1}
        else{ret}
    }
}


#[inline]
fn d(p1:(usize,usize),p2:(usize,usize))->i64{
    let y=p1.0-p2.0;
    let x=p1.1-p2.1;
    (y*y+x*x) as i64
}


const N:usize=100;
const M:usize=8;
const A:usize=5;


struct In{
    pos:[(usize,usize);N]
}
impl In{
    #[inline]
    fn input()->In{
        input!{
            n:usize,
            m:usize,
            tp:[(usize,usize);n]
        }
        assert_eq!((n,m),(N,M));

        let mut it=tp.into_iter();
        let mut pos=[(!0,!0);N];
        pos.fill_with(||it.next().unwrap());

        In{pos}
    }
}


#[derive(Clone,Copy,Default)]
struct Edge{
    dir:i64,
    tp:[i64;M],
    best:i64
}
impl Edge{
    #[inline]
    fn new(input:&In,a:usize,b:usize,m:&[(usize,usize);M])->Edge{
        let dir=A as i64*A as i64*d(input.pos[a],input.pos[b]);
        let mut best=dir;
        let mut tp=[-1;M];
        for i in 0..M{
            tp[i]=A as i64*(d(input.pos[a],m[i])+d(m[i],input.pos[b]));
            best=best.min(tp[i]);
        }

        Edge{dir,tp,best}
    }
}


#[derive(Clone)]
struct Out{
    m:[(usize,usize);M],
    route:[usize;N+1],
    dist:[[Edge;N];N]
}
impl Out{
    #[inline]
    fn new(input:&In)->Out{
        let mut route=[!0;N+1];
        let mut it=0..;
        route.fill_with(||it.next().unwrap());
        route[N]=0;
        rnd::shuffle(&mut route[1..N]);

        let m=sa1(input);

        let mut dist=[[Default::default();N];N];

        for i in 0..N{
            for j in 0..N{
                dist[i][j]=Edge::new(input,i,j,&m);
            }
        }

        Out{m,route,dist}
    }

    #[inline]
    fn score(&self)->i64{
        let mut ret=0;
        for w in self.route.windows(2){
            ret+=self.dist[w[0]][w[1]].best;
        }

        ret
    }

    #[inline]
    fn try_opt2(&self,a:usize,b:usize)->i64{
        // assert!(1<=a.min(b) && a.min(b)+1<a.max(b) && a.max(b)<self.route.len()-1);
        let a0=self.route[a-1];
        let a1=self.route[a];
        let b0=self.route[b-1];
        let b1=self.route[b];

        let old=self.dist[a0][a1].best+self.dist[b0][b1].best;
        let new=self.dist[a0][b0].best+self.dist[a1][b1].best;

        new-old
    }

    #[inline]
    fn opt2(&mut self,mut a:usize,mut b:usize){
        if a>b{
            std::mem::swap(&mut a,&mut b);
        }
        self.route[a..b].reverse();
    }
}


struct Sub{
    m:[(usize,usize);M],
    tmp:[(i64,usize);N],
    ch:[(i64,usize);N]
}
impl Sub{
    #[inline]
    fn new(input:&In)->Sub{
        let mut m=[(!0,!0);M];
        m.fill_with(||(rnd::next()%1001,rnd::next()%1001));

        let mut tmp=[(-1,!0);N];
        for (i,&p) in input.pos.iter().enumerate(){
            let mut at=!0;
            let mut dist=std::i64::MAX;
            for (i,&v) in m.iter().enumerate(){
                let d=d(p,v);
                if dist>d{
                    at=i;
                    dist=d;
                }
            }
            tmp[i]=(dist,at);
        }

        Sub{m,tmp,ch:[(-1,!0);N]}
    }

    #[inline]
    fn score(&self)->i64{
        let mut ret=0;
        for (d,_) in self.tmp{
            ret+=d;
        }
        ret
    }

    #[inline]
    // new-score
    fn change(&mut self,input:&In,add:i64,idx:usize,np:(usize,usize),score:&mut i64)->bool{
        let mut new_score=0;
        for (i,&p) in input.pos.iter().enumerate(){
            let dd=d(p,np);

            if self.tmp[i].1==idx{
                let mut mind=dd;
                let mut at=idx;
                for (j,&v) in self.m.iter().enumerate(){
                    if j!=idx{
                        let d=d(p,v);
                        if mind>d{
                            mind=d;
                            at=j;
                        }
                    }
                }
                self.ch[i]=(mind,at);
                new_score+=mind;
            }
            else{
                let cur=self.tmp[i].0;
                new_score+=cur.min(dd);
                if cur>dd{
                    self.ch[i]=(dd,idx);
                }
                else{
                    self.ch[i]=self.tmp[i];
                }
            }
        }

        if add>=new_score-*score{
            *score=new_score;
            self.m[idx]=np;
            std::mem::swap(&mut self.ch,&mut self.tmp);
            true
        }
        else{
            false
        }
    }
}


fn sa1(input:&In)->[(usize,usize);M]{
    let mut cur=Sub::new(input);
    let mut score=cur.score();
    let mut best=score;

    let mut iter=0;
    let mut up=0;
    let mut th=[0;256];

    loop{
        if iter&1023==0{
            const TL:f64=0.2;
            let p=get_time()/TL;
            if p>=1.{
                break;
            }

            const T0:f64=50000.;
            const T1:f64=0.;

            let heat=T0+(T1-T0)*p;

            th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
        }
        iter+=1;

        up+=cur.change(input,th[iter&255],rnd::next()&7,(rnd::next()%1001,rnd::next()%1001),&mut score) as usize;
        best=score.min(best);
    }

    let p=up as f64/iter as f64;
    debug!(iter,p);
    debug!(score,best);
    assert_eq!(score,cur.score());

    cur.m
}


fn sa(input:&In)->Out{
    let mut cur=Out::new(input);
    let mut score=cur.score();
    let mut best=score;

    let mut iter=0;
    let mut up=0;
    let mut th=[0;256];

    let start=get_time();

    loop{
        if iter&1023==0{
            const TL:f64=0.98;
            let p=(get_time()-start)/(TL-start);
            if p>=1.{
                break;
            }

            const T0:f64=500000.;
            const T1:f64=0.;

            let heat=T0+(T1-T0)*p;

            th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
        }
        iter+=1;

        let a=rnd::range(1,N);
        let mut b;
        while{
            b=rnd::range(1,N);
            a-b+1<=2
        }{}
        let diff=cur.try_opt2(a,b);
        
        if th[iter&255]>=diff{
            score+=diff;
            cur.opt2(a,b);
            up+=1;
            best=best.min(score);
        }
    }

    let p=up as f64/iter as f64;
    debug!(iter,p);
    debug!(score,best);
    assert_eq!(score,cur.score());

    cur
}


fn main(){
    let input=In::input();
    let out=sa(&input);

    for (a,b) in &out.m{
        println!("{a} {b}");
    }

    let mut route=vec![(1,1)];

    for w in out.route.windows(2){
        let edge=out.dist[w[0]][w[1]];
        if edge.dir!=edge.best{
            let mut t=!0;
            for (i,&m) in edge.tp.iter().enumerate(){
                if m==edge.best{
                    t=i;
                    break;
                }
            }
            route.push((2,t+1));
        }
        route.push((1,w[1]+1));
    }

    println!("{}",route.len());
    for (t,v) in route{
        println!("{t} {v}");
    }
}