結果
問題 | No.5010 Better Mo's Algorithm is Needed!! (Unweighted) |
ユーザー | rhoo |
提出日時 | 2022-12-17 23:25:45 |
言語 | Rust (1.77.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 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4,990 ms
23,360 KB |
testcase_01 | AC | 4,990 ms
23,480 KB |
testcase_02 | AC | 4,991 ms
23,352 KB |
testcase_03 | AC | 4,989 ms
23,320 KB |
testcase_04 | AC | 4,991 ms
23,496 KB |
testcase_05 | AC | 4,990 ms
23,312 KB |
testcase_06 | AC | 4,991 ms
23,436 KB |
testcase_07 | AC | 4,990 ms
23,464 KB |
testcase_08 | AC | 4,991 ms
23,376 KB |
testcase_09 | AC | 4,989 ms
23,452 KB |
testcase_10 | AC | 4,991 ms
23,456 KB |
testcase_11 | AC | 4,989 ms
23,320 KB |
testcase_12 | AC | 4,991 ms
23,404 KB |
testcase_13 | AC | 4,990 ms
23,316 KB |
testcase_14 | AC | 4,990 ms
23,356 KB |
testcase_15 | AC | 4,989 ms
23,484 KB |
testcase_16 | AC | 4,990 ms
23,448 KB |
testcase_17 | AC | 4,990 ms
23,440 KB |
testcase_18 | AC | 4,990 ms
23,216 KB |
testcase_19 | AC | 4,989 ms
23,384 KB |
testcase_20 | AC | 4,991 ms
23,476 KB |
testcase_21 | AC | 4,990 ms
23,460 KB |
testcase_22 | AC | 4,990 ms
23,412 KB |
testcase_23 | AC | 4,990 ms
23,460 KB |
testcase_24 | AC | 4,991 ms
23,492 KB |
testcase_25 | AC | 4,990 ms
23,336 KB |
testcase_26 | AC | 4,989 ms
23,468 KB |
testcase_27 | AC | 4,991 ms
23,396 KB |
testcase_28 | AC | 4,990 ms
23,484 KB |
testcase_29 | AC | 4,991 ms
23,316 KB |
testcase_30 | AC | 4,989 ms
23,380 KB |
testcase_31 | AC | 4,990 ms
23,516 KB |
testcase_32 | AC | 4,990 ms
23,468 KB |
testcase_33 | AC | 4,990 ms
23,480 KB |
testcase_34 | AC | 4,989 ms
23,452 KB |
testcase_35 | AC | 4,990 ms
23,460 KB |
testcase_36 | AC | 4,990 ms
23,468 KB |
testcase_37 | AC | 4,990 ms
23,496 KB |
testcase_38 | AC | 4,989 ms
23,360 KB |
testcase_39 | AC | 4,990 ms
23,364 KB |
testcase_40 | AC | 4,990 ms
23,348 KB |
testcase_41 | AC | 4,990 ms
23,496 KB |
testcase_42 | AC | 4,989 ms
23,468 KB |
testcase_43 | AC | 4,990 ms
23,396 KB |
testcase_44 | AC | 4,989 ms
23,364 KB |
testcase_45 | AC | 4,990 ms
23,368 KB |
testcase_46 | AC | 4,989 ms
23,248 KB |
testcase_47 | AC | 4,991 ms
23,400 KB |
testcase_48 | AC | 4,989 ms
23,324 KB |
testcase_49 | AC | 4,990 ms
23,444 KB |
testcase_50 | AC | 4,990 ms
23,476 KB |
testcase_51 | AC | 4,989 ms
23,504 KB |
testcase_52 | AC | 4,990 ms
23,312 KB |
testcase_53 | AC | 4,989 ms
23,264 KB |
testcase_54 | AC | 4,990 ms
23,364 KB |
testcase_55 | AC | 4,990 ms
23,512 KB |
testcase_56 | AC | 4,990 ms
23,240 KB |
testcase_57 | AC | 4,989 ms
23,388 KB |
testcase_58 | AC | 4,990 ms
23,452 KB |
testcase_59 | AC | 4,989 ms
23,320 KB |
testcase_60 | AC | 4,990 ms
23,404 KB |
testcase_61 | AC | 4,989 ms
23,392 KB |
testcase_62 | AC | 4,991 ms
23,292 KB |
testcase_63 | AC | 4,989 ms
23,388 KB |
testcase_64 | AC | 4,990 ms
23,180 KB |
testcase_65 | AC | 4,989 ms
23,380 KB |
testcase_66 | AC | 4,991 ms
23,444 KB |
testcase_67 | AC | 4,990 ms
23,412 KB |
testcase_68 | AC | 4,990 ms
23,480 KB |
testcase_69 | AC | 4,990 ms
23,460 KB |
testcase_70 | AC | 4,990 ms
23,412 KB |
testcase_71 | AC | 4,989 ms
23,488 KB |
testcase_72 | AC | 4,990 ms
23,380 KB |
testcase_73 | AC | 4,989 ms
23,364 KB |
testcase_74 | AC | 4,990 ms
23,456 KB |
testcase_75 | AC | 4,989 ms
23,460 KB |
testcase_76 | AC | 4,990 ms
23,328 KB |
testcase_77 | AC | 4,990 ms
23,496 KB |
testcase_78 | AC | 4,989 ms
23,428 KB |
testcase_79 | AC | 4,990 ms
23,444 KB |
testcase_80 | AC | 4,990 ms
23,312 KB |
testcase_81 | AC | 4,991 ms
23,536 KB |
testcase_82 | AC | 4,989 ms
23,404 KB |
testcase_83 | AC | 4,991 ms
23,364 KB |
testcase_84 | AC | 4,989 ms
23,368 KB |
testcase_85 | AC | 4,990 ms
23,448 KB |
testcase_86 | AC | 4,990 ms
23,252 KB |
testcase_87 | AC | 4,990 ms
23,488 KB |
testcase_88 | AC | 4,989 ms
23,292 KB |
testcase_89 | AC | 4,990 ms
23,468 KB |
testcase_90 | AC | 4,990 ms
23,512 KB |
testcase_91 | AC | 4,990 ms
23,332 KB |
testcase_92 | AC | 4,991 ms
23,496 KB |
testcase_93 | AC | 4,991 ms
23,424 KB |
testcase_94 | AC | 4,989 ms
23,528 KB |
testcase_95 | AC | 4,989 ms
23,400 KB |
testcase_96 | AC | 4,990 ms
23,448 KB |
testcase_97 | AC | 4,990 ms
23,312 KB |
testcase_98 | AC | 4,989 ms
23,400 KB |
testcase_99 | AC | 4,989 ms
23,468 KB |
testcase_100 | AC | 4,990 ms
23,424 KB |
testcase_101 | AC | 4,989 ms
23,468 KB |
testcase_102 | AC | 4,990 ms
23,356 KB |
testcase_103 | AC | 4,990 ms
23,372 KB |
testcase_104 | AC | 4,990 ms
23,344 KB |
testcase_105 | AC | 4,989 ms
23,300 KB |
testcase_106 | AC | 4,990 ms
23,380 KB |
testcase_107 | AC | 4,989 ms
23,340 KB |
testcase_108 | AC | 4,990 ms
23,356 KB |
testcase_109 | AC | 4,990 ms
23,328 KB |
testcase_110 | AC | 4,990 ms
23,320 KB |
testcase_111 | AC | 4,989 ms
23,468 KB |
testcase_112 | AC | 4,990 ms
23,456 KB |
testcase_113 | AC | 4,989 ms
23,368 KB |
testcase_114 | AC | 4,990 ms
23,468 KB |
testcase_115 | AC | 4,990 ms
23,452 KB |
testcase_116 | AC | 4,989 ms
23,400 KB |
testcase_117 | AC | 4,990 ms
23,468 KB |
testcase_118 | AC | 4,990 ms
23,468 KB |
testcase_119 | AC | 4,989 ms
23,272 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 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(); }