#783605 (Rust) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: rhoo
• 提出日時: 2022-08-01 00:40:56
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 983 ms / 1,000 ms
• コード長: 11,860 bytes
• コンパイル時間: 1,661 ms
• 実行使用メモリ: 2,996 KB
• スコア: 9,053,849
• 最終ジャッジ日時: 2022-08-01 00:41:31
• 合計ジャッジ時間: 33,887 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	983 ms; 2,996 KB
testcase_01	AC	982 ms; 2,760 KB
testcase_02	AC	983 ms; 2,876 KB
testcase_03	AC	983 ms; 2,840 KB
testcase_04	AC	983 ms; 2,692 KB
testcase_05	AC	983 ms; 2,696 KB
testcase_06	AC	983 ms; 2,940 KB
testcase_07	AC	983 ms; 2,876 KB
testcase_08	AC	983 ms; 2,896 KB
testcase_09	AC	982 ms; 2,768 KB
testcase_10	AC	983 ms; 2,768 KB
testcase_11	AC	983 ms; 2,860 KB
testcase_12	AC	983 ms; 2,984 KB
testcase_13	AC	983 ms; 2,884 KB
testcase_14	AC	983 ms; 2,892 KB
testcase_15	AC	983 ms; 2,880 KB
testcase_16	AC	983 ms; 2,860 KB
testcase_17	AC	983 ms; 2,884 KB
testcase_18	AC	983 ms; 2,844 KB
testcase_19	AC	982 ms; 2,744 KB
testcase_20	AC	983 ms; 2,632 KB
testcase_21	AC	983 ms; 2,812 KB
testcase_22	AC	982 ms; 2,916 KB
testcase_23	AC	983 ms; 2,868 KB
testcase_24	AC	983 ms; 2,924 KB
testcase_25	AC	983 ms; 2,748 KB
testcase_26	AC	983 ms; 2,888 KB
testcase_27	AC	983 ms; 2,752 KB
testcase_28	AC	983 ms; 2,748 KB
testcase_29	AC	982 ms; 2,732 KB

コンパイルメッセージ

warning: unused variable: `p`
   --> Main.rs:435:9
    |
435 |     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: variable `ac` is assigned to, but never used
   --> Main.rs:481:13
    |
481 |     let mut ac=0;
    |             ^^
    |
    = note: consider using `_ac` instead

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 rangei(a:i64,b:i64)->i64{
        (next()>>1) as i64%(b-a)+a
    }

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


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


#[inline]
fn get_dist(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
}


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();
        In{pos:[();N].map(|_|it.next().unwrap())}
    }
}


struct Out{
    m:[(usize,usize);M],
    dist:[[i64;N];N],
    cnt:[usize;N],
    route:Vec<usize>,
    log:Vec<(bool,usize)> // type,idx
}
impl Out{
    #[inline]
    fn new(input:&In)->Out{
        let mut route=(0..N).collect::<Vec<_>>();
        route.push(0);
        let mut cnt=[0;N];
        for v in &route{
            cnt[*v]+=1;
        }
        let m=[();M].map(|_|(rnd::next()%1001,rnd::next()%1001));

        let mut dist=[[std::i64::MAX>>2;N];N];
        for i in 0..N{
            for j in 0..N{
                dist[i][j]=A*A*get_dist(input.pos[i],input.pos[j]);
            }
        }
        for k in 0..N{
            for i in 0..N{
                for j in 0..N{
                    dist[i][j]=dist[i][j].min(dist[i][k]+dist[k][j]);
                }
            }
        }

        Out{m,dist,cnt,route,log:vec![]}
    }

    #[inline]
    fn score(&self,input:&In)->i64{
        self.route.windows(2).map(|w|self.dist(input,w[0],w[1])).sum::<i64>()
    }

    #[inline]
    fn dist(&self,input:&In,a:usize,b:usize)->i64{
        if a<N && b<N{
            self.dist[a][b]
        }
        else if a>=N && b>=N{
            get_dist(self.m[a-N],self.m[b-N])
        }
        else if a>=N{
            A*get_dist(self.m[a-N],input.pos[b])
        }
        else{
            A*get_dist(self.m[b-N],input.pos[a])
        }
    }

    #[inline]
    fn sub(&self,input:&In,a:usize,p:(usize,usize))->i64{
        if a<N{
            get_dist(input.pos[a],p)*A
        }
        else{
            get_dist(self.m[a-N],p)
        }
    }

    #[inline]
    // idxは+Nされたあと
    fn change(&mut self,input:&In,add:i64,id:usize,new:(usize,usize),score:&mut i64)->bool{
        self.log.clear();
        let mut prev=self.route[0];
        let mut f=false;
        let mut at=1;
        let mut diff=0;

        for &v in &self.route[1..]{
            if f{
                diff+=self.dist(input,prev,v)-self.dist(input,prev,id)-self.dist(input,id,v);
            }

            if v!=id{
                let d=self.sub(input,prev,new)+self.sub(input,v,new)-self.dist(input,prev,v);
                if 0>d{
                    diff+=d;
                    self.log.push((true,at));
                    at+=1;
                }
                prev=v;
                at+=1;
                f=false;
            }
            else{
                self.log.push((false,at));
                f=true;
            }
        }

        if add>=diff{
            *score+=diff;
            self.m[id-N]=new;
            for &(t,idx) in &self.log{
                if t{
                    self.route.insert(idx,id);
                }
                else{
                    self.route.remove(idx);
                }
            }
            true
        }
        else{
            false
        }
    }

    #[inline]
    fn try_opt2(&self,input:&In,a:usize,b:usize)->i64{
        let a0=self.route[a-1];
        let a1=self.route[a];
        let b0=self.route[b-1];
        let b1=self.route[b];

        self.dist(input,a0,b0)+self.dist(input,a1,b1)-self.dist(input,a0,a1)-self.dist(input,b0,b1)
    }

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

    #[inline]
    fn try_insert(&self,input:&In,idx:usize,v:usize)->i64{
        let v0=self.route[idx-1];
        let v1=self.route[idx];

        self.dist(input,v0,v)+self.dist(input,v,v1)-self.dist(input,v0,v1)
    }

    #[inline]
    fn insert(&mut self,idx:usize,v:usize){
        self.route.insert(idx,v);
        if v<N{
            self.cnt[v]+=1;
        }
    }

    #[inline]
    fn try_remove(&self,input:&In,idx:usize)->i64{
        let v0=self.route[idx-1];
        let v1=self.route[idx];
        let v2=self.route[idx+1];

        self.dist(input,v0,v2)-self.dist(input,v0,v1)-self.dist(input,v1,v2)
    }

    #[inline]
    fn remove(&mut self,idx:usize){
        let v=self.route.remove(idx);
        if v<N{
            self.cnt[v]-=1;
        }
    }
}


fn sa(input:&In)->([(usize,usize);M],Vec<usize>){
    let mut best=i64::MAX;
    let mut best_state=([(!0,!0);M],vec![]);

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

    const I:usize=5;
    for i in 0..I{
        let start=get_time();
        let tl=0.98*(i+1) as f64/I as f64;

        let mut cur=Out::new(input);
        let mut score=cur.score(input);

        loop{
            if iter&1023==0{
                let p=(get_time()-start)/(tl-start);
                if p>=1.{break;}

                const T0:f64=35000.;
                const T1:f64=0.;
    
                let heat=T0+(T1-T0)*p;
    
                th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
            }

            let r=rnd::nextf();

            const A:f64=0.5;// 2-opt
            const B:f64=0.2;// insert
            const C:f64=0.2;// remove
            // const D:f64=0.1;// change

            if r<=A{
                let a=rnd::range(1,cur.route.len()-1);
                let mut b;
                while{
                    b=rnd::range(1,cur.route.len()-1);
                    a-b+1<=2
                }{}
    
                let diff=cur.try_opt2(input,a,b);
                if th[iter&255]>=diff{
                    score+=diff;
                    cur.opt2(a,b);
                    up+=1;
                }
            }
            else if r<=A+B{
                let idx=rnd::range(1,cur.route.len());
                let mut v;
                while{
                    v=rnd::next()%(N+M);
                    v==cur.route[idx-1] || v==cur.route[idx]
                }{}
                let diff=cur.try_insert(input,idx,v);
                
                if th[iter&255]>=diff{
                    score+=diff;
                    cur.insert(idx,v);
                    up+=1;
                }
            }
            else if r<=A+B+C && cur.route.len()!=N+1{
                let mut idx;
                let mut iter=0;
                while{
                    iter+=1;
                    idx=rnd::range(1,cur.route.len()-1);
    
                    let v=cur.route[idx];
                    v<N && cur.cnt[v]==1
                }{}
                
                let diff=cur.try_remove(input,idx);
    
                if th[iter&255]>=diff{
                    score+=diff;
                    cur.remove(idx);
                    up+=1;
                }
            }
            else{
                const R:i64=100;
    
                let id=rnd::next()&7;
                let p=cur.m[id];
                let mut np;
                while{
                    np=(p.0+rnd::rangei(-R,R+1) as usize,p.1+rnd::rangei(-R,R+1) as usize);
                    np.0>1000 || np.1>1000
                }{}
    
                up+=cur.change(input,th[iter&255],id+N,np,&mut score) as usize;
            }
            iter+=1;
    
            if best>score{
                best=score;
                best_state=(cur.m,cur.route.clone());
            }
        }
        debug!(score);
    }

    let p=up as f64/iter as f64;
    debug!(iter,p);
    debug!(best);
    debug!(best_state.1.len());

    best_state
}


fn main(){
    let input=In::input();
    let (m,route)=sa(&input);

    let mut dist=[[std::i64::MAX>>2;N+M];N+M];
    let mut next=[[!0;N+M];N+M];
    for i in 0..N+M{
        let a=if i<N{
            input.pos[i]
        }else{
            m[i-N]
        };
        for j in 0..N+M{
            let b=if j<N{
                input.pos[j]
            }else{
                m[j-N]
            };

            dist[i][j]=get_dist(a,b)*if i<N && j<N{A*A}
            else if i>=N && j>=N{1}
            else{A};
            next[i][j]=j;
        }
    }
    for k in 0..N+M{
        for i in 0..N+M{
            for j in 0..N+M{
                if dist[i][j]>dist[i][k]+dist[k][j]{
                    next[i][j]=next[i][k];
                    dist[i][j]=dist[i][k]+dist[k][j];
                }
            }
        }
    }

    let mut ans=vec![];
    let mut ac=0;
    let mut seen=[true;N];
    seen[0]=false;
    let mut prev=0;
    for v in route[1..route.len()-1].iter().cloned()
    .filter(move |&v|v<N && {
        let f=seen[v];
        seen[v]=false;
        f
    }).chain(0..=0){
        ac+=dist[prev][v];
        while prev!=v{
            ans.push(prev);
            prev=next[prev][v];
        }
    }
    ans.push(prev);
    debug!(ac);

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

    println!("{}",ans.len());
    for v in ans{
        if v<N{
            println!("1 {}",v+1);
        }
        else{
            println!("2 {}",v-N+1);
        }
    }
}