#826596 (Rust) No.5010 Better Mo's Algorithm is Needed!! (Unweighted)

• 問題: No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
• ユーザー: rhoo
• 提出日時: 2022-12-17 23:25:45
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 4,991 ms / 5,000 ms
• コード長: 10,061 bytes
• コンパイル時間: 4,401 ms
• 実行使用メモリ: 23,536 KB
• スコア: 18,395,127,330
• 最終ジャッジ日時: 2022-12-17 23:36:49
• 合計ジャッジ時間: 650,564 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

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

コンパイルメッセージ

warning: unused macro definition: `debug`
  --> Main.rs:88:14
   |
88 | macro_rules! debug{
   |              ^^^^^
   |
   = note: `#[warn(unused_macros)]` on by default

warning: unused macro definition: `param`
   --> Main.rs:152:14
    |
152 | macro_rules! param{
    |              ^^^^^

warning: unused import: `std::mem`
   --> Main.rs:203:5
    |
203 | use std::mem;
    |     ^^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `p`
   --> Main.rs:447:9
    |
447 |     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: type alias is never used: `Ptr`
   --> Main.rs:221:1
    |
221 | type Ptr=Rc<RefCell<List>>;
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: variant is never constructed: `Yes`
   --> Main.rs:225:5
    |
225 |     Yes(usize),
    |     ^^^^^^^^^^

warning: variant is never constructed: `No`
   --> Main.rs:226:5
    |
226 |     No,
    |     ^^

warning: struct is never constructed: `List`
   --> Main.rs:231:8
    |
231 | struct List{
    |        ^^^^

warning: associated function is never used: `new`
   --> Main.rs:239:8
    |
239 |     fn new(v:(usize,usize,usize))->Ptr{
    |        ^^^

warning: associated function is never used: `insert_next`
   --> Main.rs:244:8
    |
244 |     fn insert_next(&mut self,v:(usize,usize,usize))->Ptr{
    |        ^^^^^^^^^^^

warning: associated function is never used: `collect_vec_`
   --> Main.rs:255:8
    |
255 |     fn collect_vec_(&self)->Vec<(usize,usize,usize)>{
    |        ^^^^^^^^^^^^

warning: associated function is never used: `get_next`
   --> Main.rs:268:8
    |
268 |     fn get_next(&self,idx:usize)->Option<Ptr>{
    |        ^^^^^^^^

warning: field is never read: `st`
   --> Main.rs:286:5
    |
286 |     st:usize,
    |     ^^^^^^^^

warning: associated function is never used: 

ソースコード

#![allow(non_snake_case)]


#[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.
        }
    }
    
    #[inline]
    pub fn range(a:usize,b:usize)->usize{
        next()%(b-a)+a
    }
    
    #[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]
    pub fn shuffle<T>(list:&mut [T]){
        for i in (0..list.len()).rev(){
            list.swap(i,next()%(i+1));
        }
    }
}


#[inline]
fn get_time_secs()->f64{
    std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64()
}


struct Timer(f64);
impl Timer{
    #[inline]
    fn new()->Timer{
        Timer(get_time_secs())
    }

    #[inline]
    fn get_time(&self)->f64{
        get_time_secs()-self.0
    }
}


#[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))]
macro_rules! debug{
    ($($_:tt)*)=>{}
}


#[cfg(local)]
macro_rules! log{
    ()=>{};

    ($x:literal)=>{
        eprintln!("{}",$x);
    };
    
    ($x:ident $(,)?)=>{
        log!(@out $x,$x);
    };
    ($x:ident,$t:ident $(,)?)=>{
        log!(@out $x,$x);
        log!($t);
    };
    ($x:ident,$($_:ident).* $(,)?)=>{
        compile_error!();
    };
    ($x:ident,$t:expr $(,)?)=>{
        log!(@out $x,$t);
    };
    ($($x:ident).* $(,)?)=>{
        log!(@last $($x).*;$($x).*);
    };

    ($x:ident,$t:ident,$($rest:tt)*)=>{
        log!(@out $x,$x);
        log!($t,$($rest)*);
    };
    ($x:ident,$($_:ident).*,$($rest:tt)*)=>{
        compile_error!();
    };
    ($x:ident,$t:expr,$($rest:tt)*)=>{
        log!(@out $x,$t);
        log!($($rest)*);
    };
    ($($x:ident).*,$($rest:tt)*)=>{
        log!(@last $($x).*;$($x).*);
        log!($($rest)*);
    };

    (@out $x:ident,$t:expr)=>{
        eprintln!("{} = {:?}",stringify!($x),$t);
    };

    (@last $x:ident;$full:expr)=>{
        log!(@out $x,$full);
    };
    (@last $_:ident. $($rest:ident).*;$full:expr)=>{
        log!(@last $($rest).*;$full)
    }
}

#[cfg(not(local))]
macro_rules! log{
    ($($_:tt)*)=>{}
}


macro_rules! param{
    ($($x:ident:$t:ty=$v:literal),* $(,)?)=>{
        #[allow(non_snake_case)]
        struct Param{
            $($x:$t),*
        }
        impl Param{
            #[inline]
            fn new()->Self{
                Self{
                    $(
                        $x:match std::env::var(stringify!($x)){
                            Ok(s)=>s.parse().expect("parse error"),
                            Err(_)=>$v
                        }
                    ),*
                }
            }
        }
    };
}


#[allow(unused)]
struct Scanner{
    stack:std::str::SplitAsciiWhitespace<'static>
}
#[allow(unused)]
impl Scanner{
    #[inline]
    fn new()->Self{
        Self{stack:"".split_ascii_whitespace()}
    }

    #[inline]
    fn read<T:std::str::FromStr>(&mut self)->T{
        loop{
            if let Some(v)=self.stack.next(){
                return v.parse::<T>().unwrap_or_else(|_|panic!("{}: parse error",std::any::type_name::<T>()));
            }

            let mut tmp=String::new();
            std::io::stdin().read_line(&mut tmp).unwrap();
            assert!(!tmp.is_empty());
            self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
        }
    }
}


use std::io::*;
use std::mem;
use std::cmp::Reverse;


const N:usize=200000;
const Q:usize=200000;


#[inline]
fn abs_diff(a:usize,b:usize)->usize{
    (a as i64-b as i64).abs() as usize
}


use std::rc::Rc;
use std::cell::RefCell;


type Ptr=Rc<RefCell<List>>;

#[derive(Clone,PartialEq,Debug)]
enum CheckPoint{
    Yes(usize),
    No,
}
use CheckPoint::*;


struct List{
    prev:Option<Ptr>,
    v:(usize,usize,usize),
    cp:CheckPoint,
    next:Option<Ptr>,
}
impl List{
    #[inline]
    fn new(v:(usize,usize,usize))->Ptr{
        Rc::new(RefCell::new(List{prev:None,v,next:None,cp:No}))
    }

    #[inline]
    fn insert_next(&mut self,v:(usize,usize,usize))->Ptr{
        let ret=Rc::new(RefCell::new(List{prev:self.prev.clone(),v,next:self.next.clone(),cp:No}));
        if let Some(next)=self.next.clone(){
            next.borrow_mut().prev=Some(ret.clone());
        }
        self.next=Some(ret.clone());
        
        ret
    }

    #[inline]
    fn collect_vec_(&self)->Vec<(usize,usize,usize)>{
        let mut ret=vec![self.v];
        let mut ptr=self.next.clone();
        while let Some(np)=ptr{
            let np=np.borrow();
            ret.push(np.v);
            ptr=np.next.clone();
        }

        ret
    }

    #[inline]
    fn get_next(&self,idx:usize)->Option<Ptr>{
        assert!(1<=idx);
        let mut ptr=self.next.clone();
        for _ in 1..idx{
            if ptr.is_none(){
                return None;
                // debug!(t);
                // panic!();
            }
            ptr=ptr.unwrap().borrow().next.clone();
        }

        ptr//.unwrap()
    }
}


struct Out{
    st:usize,
    route:Vec<(usize,usize,usize)>
}
impl Out{
    #[inline]
    fn input()->Out{
        let mut scan=Scanner::new();
        let n:usize=scan.read();
        let q:usize=scan.read();
        let wt:usize=scan.read();
        let st:usize=scan.read();
        assert_eq!((n,q,wt),(N,Q,1));
        for _ in 0..n{
            scan.read::<usize>();
        }

        let mut route=Vec::with_capacity(Q);
        for i in 0..Q{
            let l:usize=scan.read();
            let r:usize=scan.read();
            route.push((l,r,i));
        }

        Out{st,route}
    }

    #[inline]
    fn greedy(&mut self){
        const D:usize=10;
        let arg_max=(0..Q).max_by_key(|&i|{
            let (l,r,_)=self.route[i];
            (l/D,r/D,Reverse(r-l))
        }).unwrap();
        let mut new_route=Vec::with_capacity(Q);
        new_route.push(self.route[arg_max]);
        self.route.swap(0,arg_max);

        self.route[1..].sort_unstable();
        let mut block0=vec![Vec::with_capacity(Q/D);D];
        let w=Q/D;
        for i in 1..Q{
            block0[(i/w).min(D-1)].push(self.route[i]);
        }
        let mut block1=vec![vec![Vec::with_capacity(Q/(D*D));D];D];
        for i in 0..D{
            block0[i].sort_unstable_by_key(|(_,r,_)|*r);
            let w=block0[i].len()/D;
            for j in 0..block0[i].len(){
                block1[i][(j/w).min(D-1)].push(block0[i][j]);
            }
        }
        let mut blocks=Vec::with_capacity(D*D);
        for (i,b0) in block1.into_iter().enumerate(){
            for (j,b1) in b0.into_iter().enumerate(){
                blocks.push((i,j,b1));
            }
        }
        blocks.sort_unstable_by_key(|&(y,x,_)|{
            if D&1==y&1{
                Reverse((y,!x))
            }
            else{
                Reverse((y,x))
            }
        });

        self.route.truncate(1);
        for (_,_,mut block) in blocks{
            while !block.is_empty(){
                let last=self.route.last().unwrap().clone();
                let arg_max=(0..block.len()).min_by_key(|&i|self.get(last,block[i])).unwrap();
                self.route.push(block.swap_remove(arg_max));
            }
        }

        assert_eq!(self.route.len(),Q);
    }

    #[inline]
    fn score(&self)->i64{
        let mut ret=self.route[0].1-self.route[0].0;

        for i in 1..self.route.len(){
            ret+=self.dist(i-1,i);
        }

        ret as i64
    }

    #[inline]
    fn get(&self,(l0,r0,_):(usize,usize,usize),(l1,r1,_):(usize,usize,usize))->usize{
        abs_diff(l0,l1)+abs_diff(r0,r1)
    }

    #[inline]
    fn dist(&self,a:usize,b:usize)->usize{
        self.get(self.route[a],self.route[b])
    }

    #[inline]
    fn try_2opt(&self,a:usize,b:usize)->i64{
        let old=self.dist(a-1,a)+self.dist(b-1,b);
        let new=self.dist(a-1,b-1)+self.dist(a,b);
        (new-old) as i64
    }

    #[inline]
    fn apply_2opt(&mut self,a:usize,b:usize){
        self.route[a..b].reverse()
    }
}


fn sa(out:&mut Out,time:&Timer){
    let mut score=0;
    let mut best=score;

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

    const D:usize=500;

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

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

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

            let mut id=0;
            while{
                th[id]=(-heat*rnd::nextf().ln()) as i64;
                th[id+1]=(-heat*rnd::nextf().ln()) as i64;
                id+=2;
                id<th.len()
            }{}
        }
        iter+=1;

        a+=1;
        if Q-D-1<=a{
            a=1;
        }
        let b=a+rnd::next()%D+1;

        let diff=out.try_2opt(a,b);

        if diff<=th[iter&255]{
            out.apply_2opt(a,b);
            score+=diff;
            up+=1;
            best=best.min(score);
        }
    }

    let p=up as f64/iter as f64;
    log!(score,best,iter,iter as f64/1e7,p);

    log!(scoref,out.score() as f64/1e6);
}


fn main(){
    let time=Timer::new();
    let mut out=Out::input();
    out.greedy();
    log!(init_score,out.score() as f64/1e6);

    sa(&mut out,&time);

    let stdout=stdout();
    let stdout=&mut BufWriter::new(stdout.lock());
    for (_,_,id) in &out.route{
        writeln!(stdout,"{}",id+1).unwrap();
    }
    stdout.flush().unwrap();
}