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

提出ソース

結果

問題	No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
ユーザー	rhoo
提出日時	2022-12-17 01:26:08
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	4,992 ms / 5,000 ms
コード長	6,691 bytes
コンパイル時間	2,348 ms
実行使用メモリ	13,764 KB
スコア	9,575,428,585
最終ジャッジ日時	2022-12-17 01:36:55
合計ジャッジ時間	645,635 ms
ジャッジサーバーID （参考情報）	judge15 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4,989 ms 13,644 KB
testcase_01	AC	4,990 ms 13,628 KB
testcase_02	AC	4,989 ms 13,480 KB
testcase_03	AC	4,989 ms 13,620 KB
testcase_04	AC	4,989 ms 13,764 KB
testcase_05	AC	4,989 ms 13,600 KB
testcase_06	AC	4,990 ms 13,376 KB
testcase_07	AC	4,989 ms 13,736 KB
testcase_08	AC	4,989 ms 13,364 KB
testcase_09	AC	4,989 ms 13,596 KB
testcase_10	AC	4,989 ms 13,640 KB
testcase_11	AC	4,990 ms 13,404 KB
testcase_12	AC	4,989 ms 13,408 KB
testcase_13	AC	4,990 ms 13,304 KB
testcase_14	AC	4,989 ms 13,612 KB
testcase_15	AC	4,990 ms 13,448 KB
testcase_16	AC	4,989 ms 13,364 KB
testcase_17	AC	4,990 ms 13,448 KB
testcase_18	AC	4,989 ms 13,460 KB
testcase_19	AC	4,989 ms 13,308 KB
testcase_20	AC	4,989 ms 13,664 KB
testcase_21	AC	4,989 ms 13,540 KB
testcase_22	AC	4,991 ms 13,532 KB
testcase_23	AC	4,989 ms 13,580 KB
testcase_24	AC	4,989 ms 13,528 KB
testcase_25	AC	4,990 ms 13,604 KB
testcase_26	AC	4,990 ms 13,480 KB
testcase_27	AC	4,990 ms 13,464 KB
testcase_28	AC	4,989 ms 13,540 KB
testcase_29	AC	4,990 ms 13,464 KB
testcase_30	AC	4,989 ms 13,624 KB
testcase_31	AC	4,990 ms 13,596 KB
testcase_32	AC	4,989 ms 13,536 KB
testcase_33	AC	4,992 ms 13,552 KB
testcase_34	AC	4,990 ms 13,600 KB
testcase_35	AC	4,989 ms 13,560 KB
testcase_36	AC	4,990 ms 13,556 KB
testcase_37	AC	4,989 ms 13,468 KB
testcase_38	AC	4,990 ms 13,632 KB
testcase_39	AC	4,988 ms 13,480 KB
testcase_40	AC	4,990 ms 13,620 KB
testcase_41	AC	4,989 ms 13,580 KB
testcase_42	AC	4,990 ms 13,556 KB
testcase_43	AC	4,989 ms 13,596 KB
testcase_44	AC	4,990 ms 13,532 KB
testcase_45	AC	4,989 ms 13,620 KB
testcase_46	AC	4,989 ms 13,568 KB
testcase_47	AC	4,989 ms 13,612 KB
testcase_48	AC	4,989 ms 13,604 KB
testcase_49	AC	4,990 ms 13,512 KB
testcase_50	AC	4,990 ms 13,580 KB
testcase_51	AC	4,989 ms 13,616 KB
testcase_52	AC	4,990 ms 13,580 KB
testcase_53	AC	4,989 ms 13,480 KB
testcase_54	AC	4,990 ms 13,524 KB
testcase_55	AC	4,989 ms 13,540 KB
testcase_56	AC	4,990 ms 13,472 KB
testcase_57	AC	4,989 ms 13,464 KB
testcase_58	AC	4,989 ms 13,512 KB
testcase_59	AC	4,989 ms 13,596 KB
testcase_60	AC	4,989 ms 13,464 KB
testcase_61	AC	4,990 ms 13,480 KB
testcase_62	AC	4,989 ms 13,524 KB
testcase_63	AC	4,989 ms 13,532 KB
testcase_64	AC	4,990 ms 13,600 KB
testcase_65	AC	4,989 ms 13,532 KB
testcase_66	AC	4,990 ms 13,608 KB
testcase_67	AC	4,988 ms 13,416 KB
testcase_68	AC	4,990 ms 13,460 KB
testcase_69	AC	4,989 ms 13,588 KB
testcase_70	AC	4,990 ms 13,468 KB
testcase_71	AC	4,989 ms 13,528 KB
testcase_72	AC	4,990 ms 13,508 KB
testcase_73	AC	4,990 ms 13,544 KB
testcase_74	AC	4,989 ms 13,608 KB
testcase_75	AC	4,989 ms 13,532 KB
testcase_76	AC	4,989 ms 13,412 KB
testcase_77	AC	4,989 ms 13,484 KB
testcase_78	AC	4,989 ms 13,576 KB
testcase_79	AC	4,990 ms 13,560 KB
testcase_80	AC	4,989 ms 13,508 KB
testcase_81	AC	4,990 ms 13,468 KB
testcase_82	AC	4,989 ms 13,480 KB
testcase_83	AC	4,989 ms 13,592 KB
testcase_84	AC	4,989 ms 13,524 KB
testcase_85	AC	4,989 ms 13,576 KB
testcase_86	AC	4,990 ms 13,560 KB
testcase_87	AC	4,990 ms 13,552 KB
testcase_88	AC	4,989 ms 13,536 KB
testcase_89	AC	4,990 ms 13,568 KB
testcase_90	AC	4,988 ms 13,396 KB
testcase_91	AC	4,990 ms 13,572 KB
testcase_92	AC	4,989 ms 13,536 KB
testcase_93	AC	4,990 ms 13,576 KB
testcase_94	AC	4,989 ms 13,576 KB
testcase_95	AC	4,990 ms 13,548 KB
testcase_96	AC	4,989 ms 13,448 KB
testcase_97	AC	4,990 ms 13,444 KB
testcase_98	AC	4,989 ms 13,532 KB
testcase_99	AC	4,989 ms 13,484 KB
testcase_100	AC	4,989 ms 13,620 KB
testcase_101	AC	4,989 ms 13,608 KB
testcase_102	AC	4,990 ms 13,468 KB
testcase_103	AC	4,989 ms 13,568 KB
testcase_104	AC	4,990 ms 13,420 KB
testcase_105	AC	4,990 ms 13,604 KB
testcase_106	AC	4,989 ms 13,464 KB
testcase_107	AC	4,990 ms 13,540 KB
testcase_108	AC	4,989 ms 13,576 KB
testcase_109	AC	4,990 ms 13,580 KB
testcase_110	AC	4,989 ms 13,528 KB
testcase_111	AC	4,990 ms 13,512 KB
testcase_112	AC	4,990 ms 13,472 KB
testcase_113	AC	4,989 ms 13,536 KB
testcase_114	AC	4,990 ms 13,528 KB
testcase_115	AC	4,989 ms 13,648 KB
testcase_116	AC	4,989 ms 13,496 KB
testcase_117	AC	4,989 ms 13,488 KB
testcase_118	AC	4,990 ms 13,464 KB
testcase_119	AC	4,989 ms 13,532 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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 variable: `p`
   --> Main.rs:318:9
    |
318 |     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: field is never read: `st`
   --> Main.rs:217:5
    |
217 |     st:usize,
    |     ^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: associated function is never used: `score`
   --> Main.rs:256:8
    |
256 |     fn score(&self)->i64{
    |        ^^^^^

warning: 5 warnings emitted

ソースコード

raw source code

#![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;


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
}


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);
        let mut min_dist=!0;
        let mut arg_min=!0;
        for i in 0..Q{
            let l:usize=scan.read();
            let r:usize=scan.read();
            route.push((l,r,i));
            let dist=r-l;
            if min_dist>dist{
                min_dist=dist;
                arg_min=i;
            }
        }
        route.swap(0,arg_min);

        route[1..].sort_unstable_by_key(|(l,r,_)|{
            (l>>9,r>>9)
        });
        
        Out{st,route}
    }

    #[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 dist(&self,a:usize,b:usize)->usize{
        let (l0,r0,_)=self.route[a];
        let (l1,r1,_)=self.route[b];

        abs_diff(l0,l1)+abs_diff(r0,r1)
    }

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

    #[inline]
    fn apply_2opt(&mut self,mut a:usize,mut b:usize){
        if a>b{
            mem::swap(&mut a,&mut b);
        }

        self.route[a..b].reverse()
    }
}


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

    let mut iter=0;
    let mut up=0;

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

        let a=rnd::range(1,Q);
        let b=rnd::range(1,Q);

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

        if diff<=0{
            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,p);

    log!(scoref,out.score());
}


fn main(){
    let time=Timer::new();
    let mut out=Out::input();

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード