結果

問題 No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
ユーザー rhoorhoo
提出日時 2022-12-18 01:17:32
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 3,869 ms / 5,000 ms
コード長 7,208 bytes
コンパイル時間 3,837 ms
実行使用メモリ 23,820 KB
スコア 19,027,733,458
最終ジャッジ日時 2022-12-18 01:28:54
合計ジャッジ時間 508,139 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,807 ms
23,704 KB
testcase_01 AC 3,786 ms
23,660 KB
testcase_02 AC 3,859 ms
23,608 KB
testcase_03 AC 3,812 ms
23,616 KB
testcase_04 AC 3,808 ms
23,612 KB
testcase_05 AC 3,807 ms
23,756 KB
testcase_06 AC 3,809 ms
23,732 KB
testcase_07 AC 3,816 ms
23,604 KB
testcase_08 AC 3,815 ms
23,684 KB
testcase_09 AC 3,812 ms
23,616 KB
testcase_10 AC 3,806 ms
23,732 KB
testcase_11 AC 3,808 ms
23,724 KB
testcase_12 AC 3,810 ms
23,776 KB
testcase_13 AC 3,803 ms
23,708 KB
testcase_14 AC 3,811 ms
23,584 KB
testcase_15 AC 3,837 ms
23,676 KB
testcase_16 AC 3,809 ms
23,720 KB
testcase_17 AC 3,807 ms
23,664 KB
testcase_18 AC 3,813 ms
23,700 KB
testcase_19 AC 3,797 ms
23,732 KB
testcase_20 AC 3,795 ms
23,660 KB
testcase_21 AC 3,798 ms
23,684 KB
testcase_22 AC 3,802 ms
23,756 KB
testcase_23 AC 3,814 ms
23,688 KB
testcase_24 AC 3,810 ms
23,604 KB
testcase_25 AC 3,808 ms
23,728 KB
testcase_26 AC 3,814 ms
23,636 KB
testcase_27 AC 3,829 ms
23,612 KB
testcase_28 AC 3,809 ms
23,712 KB
testcase_29 AC 3,811 ms
23,676 KB
testcase_30 AC 3,798 ms
23,660 KB
testcase_31 AC 3,813 ms
23,652 KB
testcase_32 AC 3,804 ms
23,696 KB
testcase_33 AC 3,822 ms
23,692 KB
testcase_34 AC 3,869 ms
23,748 KB
testcase_35 AC 3,806 ms
23,684 KB
testcase_36 AC 3,815 ms
23,820 KB
testcase_37 AC 3,817 ms
23,612 KB
testcase_38 AC 3,825 ms
23,692 KB
testcase_39 AC 3,817 ms
23,608 KB
testcase_40 AC 3,809 ms
23,612 KB
testcase_41 AC 3,842 ms
23,680 KB
testcase_42 AC 3,805 ms
23,712 KB
testcase_43 AC 3,807 ms
23,688 KB
testcase_44 AC 3,833 ms
23,624 KB
testcase_45 AC 3,809 ms
23,632 KB
testcase_46 AC 3,812 ms
23,812 KB
testcase_47 AC 3,810 ms
23,692 KB
testcase_48 AC 3,812 ms
23,676 KB
testcase_49 AC 3,809 ms
23,684 KB
testcase_50 AC 3,812 ms
23,676 KB
testcase_51 AC 3,811 ms
23,696 KB
testcase_52 AC 3,814 ms
23,604 KB
testcase_53 AC 3,815 ms
23,632 KB
testcase_54 AC 3,794 ms
23,700 KB
testcase_55 AC 3,801 ms
23,744 KB
testcase_56 AC 3,788 ms
23,652 KB
testcase_57 AC 3,816 ms
23,588 KB
testcase_58 AC 3,804 ms
23,680 KB
testcase_59 AC 3,839 ms
23,688 KB
testcase_60 AC 3,813 ms
23,656 KB
testcase_61 AC 3,811 ms
23,744 KB
testcase_62 AC 3,817 ms
23,732 KB
testcase_63 AC 3,812 ms
23,676 KB
testcase_64 AC 3,814 ms
23,604 KB
testcase_65 AC 3,863 ms
23,756 KB
testcase_66 AC 3,819 ms
23,656 KB
testcase_67 AC 3,814 ms
23,688 KB
testcase_68 AC 3,809 ms
23,608 KB
testcase_69 AC 3,820 ms
23,668 KB
testcase_70 AC 3,816 ms
23,656 KB
testcase_71 AC 3,794 ms
23,712 KB
testcase_72 AC 3,798 ms
23,696 KB
testcase_73 AC 3,840 ms
23,768 KB
testcase_74 AC 3,808 ms
23,700 KB
testcase_75 AC 3,808 ms
23,692 KB
testcase_76 AC 3,809 ms
23,644 KB
testcase_77 AC 3,815 ms
23,700 KB
testcase_78 AC 3,817 ms
23,720 KB
testcase_79 AC 3,787 ms
23,636 KB
testcase_80 AC 3,783 ms
23,648 KB
testcase_81 AC 3,808 ms
23,740 KB
testcase_82 AC 3,812 ms
23,656 KB
testcase_83 AC 3,806 ms
23,640 KB
testcase_84 AC 3,782 ms
23,688 KB
testcase_85 AC 3,821 ms
23,664 KB
testcase_86 AC 3,812 ms
23,612 KB
testcase_87 AC 3,838 ms
23,652 KB
testcase_88 AC 3,836 ms
23,696 KB
testcase_89 AC 3,772 ms
23,652 KB
testcase_90 AC 3,780 ms
23,696 KB
testcase_91 AC 3,804 ms
23,604 KB
testcase_92 AC 3,789 ms
23,608 KB
testcase_93 AC 3,807 ms
23,680 KB
testcase_94 AC 3,811 ms
23,604 KB
testcase_95 AC 3,809 ms
23,780 KB
testcase_96 AC 3,819 ms
23,756 KB
testcase_97 AC 3,865 ms
23,628 KB
testcase_98 AC 3,798 ms
23,636 KB
testcase_99 AC 3,784 ms
23,748 KB
testcase_100 AC 3,806 ms
23,720 KB
testcase_101 AC 3,812 ms
23,708 KB
testcase_102 AC 3,809 ms
23,688 KB
testcase_103 AC 3,841 ms
23,684 KB
testcase_104 AC 3,816 ms
23,660 KB
testcase_105 AC 3,815 ms
23,616 KB
testcase_106 AC 3,819 ms
23,820 KB
testcase_107 AC 3,819 ms
23,676 KB
testcase_108 AC 3,812 ms
23,696 KB
testcase_109 AC 3,813 ms
23,608 KB
testcase_110 AC 3,814 ms
23,604 KB
testcase_111 AC 3,859 ms
23,784 KB
testcase_112 AC 3,831 ms
23,624 KB
testcase_113 AC 3,822 ms
23,672 KB
testcase_114 AC 3,818 ms
23,680 KB
testcase_115 AC 3,826 ms
23,680 KB
testcase_116 AC 3,822 ms
23,660 KB
testcase_117 AC 3,855 ms
23,612 KB
testcase_118 AC 3,807 ms
23,696 KB
testcase_119 AC 3,806 ms
23,652 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused macro definition: `param`
  --> Main.rs:83:14
   |
83 | macro_rules! param{
   |              ^^^^^
   |
   = note: `#[warn(unused_macros)]` on by default

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

warning: unused variable: `st`
   --> Main.rs:159:13
    |
159 |         let st:usize=scan.read();
    |             ^^ help: if this is intentional, prefix it with an underscore: `_st`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: field is never read: `st`
   --> Main.rs:149:5
    |
149 |     st:usize,
    |     ^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

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

warning: 5 warnings emitted

ソースコード

diff # 

#![allow(non_snake_case)]


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


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:0,route}
    }

    #[inline]
    fn greedy(&mut self){
        const D:usize=15;
        self.route[1..].sort_unstable();
        let mut block0=vec![Vec::with_capacity(Q/D);D];
        let w=Q/D;
        for i in 0..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.clear();
        for (_,_,mut block) in blocks{
            while !block.is_empty(){
                let arg_max=if self.route.is_empty(){
                    (0..block.len()).min_by_key(|&i|self.get_first(block[i])).unwrap()
                }
                else{
                    let last=self.route.last().unwrap().clone();
                    (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.get_first(self.route[0]);

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

        ret as i64
    }

    #[inline]
    fn get_first(&self,(l,r,_):(usize,usize,usize))->usize{
        l-r
    }

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


const TL:f64=1.98;

fn hc(out:&mut Out,d:usize){
    for a in 1..Q-d{
        for b in a+2..a+d{
            let diff=out.try_2opt(a,b);
            if diff<=0{
                out.apply_2opt(a,b);
            }
        }
    }

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

fn hc_with_timer(out:&mut Out,time:&Timer,d:usize){
    let mut iter=0;
    for a in 1..Q-d{
        for b in a+2..a+d{
            if iter&255==0 && time.get_time()>=TL{
                return;
            }
            iter+=1;
            let diff=out.try_2opt(a,b);
            if diff<=0{
                out.apply_2opt(a,b);
            }
        }
    }

    log!(score,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);

    hc(&mut out,900);
    hc(&mut out,900);
    hc_with_timer(&mut out,&time,200);
    hc_with_timer(&mut out,&time,200);
    hc_with_timer(&mut out,&time,200);
    hc_with_timer(&mut out,&time,200);
    hc_with_timer(&mut out,&time,500);

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