結果
問題 | No.5019 Hakai Project |
ユーザー |
|
提出日時 | 2023-11-19 19:48:17 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2,969 ms / 3,000 ms |
コード長 | 44,409 bytes |
コンパイル時間 | 7,312 ms |
コンパイル使用メモリ | 231,260 KB |
実行使用メモリ | 171,776 KB |
スコア | 2,932,000,086 |
最終ジャッジ日時 | 2023-11-19 19:51:02 |
合計ジャッジ時間 | 163,689 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
コンパイルメッセージ
warning: variable `valid` is assigned to, but never used --> Main.rs:718:17 | 718 | let mut valid=0; | ^^^^^ | = note: consider using `_valid` instead = note: `#[warn(unused_variables)]` on by default warning: constant `M` is never used --> Main.rs:770:7 | 770 | const M:usize=20; | ^ | = note: `#[warn(dead_code)]` on by default warning: field `ratio` is never read --> Main.rs:809:5 | 799 | struct Input{ | ----- field in this struct ... 809 | ratio:f64, | ^^^^^ warning: field `dx` is never read --> Main.rs:1061:5 | 1057 | struct StaticGrid<T,const N:usize,const M:usize,const SIZE:usize>{ | ---------- field in this struct ... 1061 | dx:[usize;8], | ^^ | = note: `StaticGrid` has a derived impl for the trait `Clone`, but this is intentionally ignored during dead code analysis warning: method `set_wall` is never used --> Main.rs:1100:8 | 1063 | impl<T,const N:usize,const M:usize,const SIZE:usize> StaticGrid<T,N,M,SIZE>{ | --------------------------------------------------------------------------- method in this implementation ... 1100 | fn set_wall(&mut self,p:usize,f:bool){ | ^^^^^^^^ warning: methods `dot`, `det`, `abs2`, and `rot90` are never used --> Main.rs:1161:8 | 1152 | impl P{ | ------ methods in this implementation ... 1161 | fn dot(self,a:P)->i64{ | ^^^ ... 1165 | fn det(self,a:P)->i64{ | ^^^ ... 1173 | fn abs2(self)->i64{ | ^^^^ ... 1178 | fn rot90(self)->P{ | ^^^^^ warning: method `clear` is never used --> Main.rs:1375:8 | 1328 | impl IndexSet{ | ------------- method in this implementation ... 1375 | fn clear(&mut self){ | ^^^^^ warning: methods `len` and `to_slice` are never used --> Main.rs:1414:8 | 1397 | impl<T> Queue<T>{ | ---------------- methods in thi
ソースコード
#![allow(non_snake_case)]fn main(){get_time();let input=Input::new();let ans=solve(&input);eprintln!("timer = {}",unsafe{TIME});write_output(&ans);}fn solve(input:&Input)->Vec<Cmd>{let state=State::new(input);let mut solver=SA::new(state);let res=solver.solve(input,2.5,10);// todo: 乱数を足すか、それとも// let res=(0..res.len()).step_by(2).map(|i|res[i].clone()).collect::<Vec<_>>();let mut best=vec![];let mut best_score=INF;for (tl,state) in multi_start_iter(res.len(),2.95).zip(res.into_iter()){let (ans,score)=solve_tsp(input,state,tl);// eprintln!("# {}",score);if best_score>score{best_score=score;best=ans;}}eprintln!("score = {}",best_score);best}fn solve_tsp(input:&Input,a:Vec<usize>,tl:f64)->(Vec<Cmd>,i64){let start=a.len();let goal=a.len()+1;let med=a.len()+2;const INF:i64=i64::MAX/32;let mut dist=vec![vec![0;a.len()+3];a.len()+3];for i in 0..a.len(){for j in 0..a.len(){dist[i][j]=(input.pos[a[i]].0-input.pos[a[j]].0).manh();}}for i in 0..a.len(){dist[i][start]=(input.pos[a[i]].0-START).manh();dist[start][i]=dist[i][start];dist[i][med]=INF;dist[med][i]=INF;}let mut a={let route=solve_tsp_greedy(&dist,start);let mut route=solve_tsp_ils(&dist,route);assert!(&route[..3]==&[start,med,goal] || &route[route.len()-3..]==&[goal,med,start]);if &route[..3]==&[start,med,goal]{let idx=route.len()-1;route[1..idx].reverse();}let mut new=vec![!0;a.len()];for (i,&n) in route[1..route.len()-3].iter().enumerate(){new[i]=a[n];}new};let mut DP=InsertionDP::new(input,&a);let mut score=DP.solve(input,a.iter().copied());let dist=|a:usize,b:usize|->i64{if a&b==!0{INF} else if a==!0{(START-input.pos[b].0).manh()} else if b==!0{0} else{(input.pos[a].0-input.pos[b].0).manh()}};// let mut t=vec![];while get_time()<=tl{let r=rnd::nextf();if r<=0.4{ // todolet (i,j)=(0..10).map(|_|{let mut i=rnd::next()%(a.len()+1);let mut j;loop{j=rnd::range_skip(0,a.len()+1,i);let abs=(i as i64-j as i64).abs();if 1<abs{break;}}if i>j{(i,j)=(j,i);}(i,j)}).min_by_key(|&(i,j)|{let (i0,i1)=(a.get(i-1).copied().unwrap_or(!0),a[i]);let (j0,j1)=(a[j-1],a.get(j).copied().unwrap_or(!0));dist(i0,j1)+dist(i1,j0)-dist(i0,i1)-dist(j0,j1)}).unwrap();let new=DP.solve(input,a[..i].iter().chain(a[i..j].iter().rev()).chain(&a[j..]).copied());if score>=new{score=new;a[i..j].reverse();}} else{ // todolet (i,j,k)=(0..10).map(|_|{let is;loop{let mut a=[rnd::next()%(a.len()+1),rnd::next()%(a.len()+1),rnd::next()%(a.len()+1)];a.sort_unstable();if a[0]+1<a[1] && a[1]+1<a[2]{is=a;break;}}(is[0],is[1],is[2])}).min_by_key(|&(i,j,k)|{let (i0,i1)=(a.get(i-1).copied().unwrap_or(!0),a[i]);let (j0,j1)=(a[j-1],a[j]);let (k0,k1)=(a[k-1],a.get(k).copied().unwrap_or(!0));dist(i0,j1)+dist(k0,i1)+dist(j0,k1)-dist(i0,i1)-dist(j0,j1)-dist(k0,k1)}).unwrap();let new=DP.solve(input,a[..i].iter().chain(&a[j..k]).chain(&a[i..j]).chain(&a[k..]).copied());if score>=new{score=new;a[i..k].rotate_left(j-i);}}}DP.solve(input,a.iter().copied());let res=DP.restore();let mut route=vec![(START,!0,0,vec![])];for i in 0..a.len(){if res[i]!=!0{route.push((input.shop[res[i]],!0,0,vec![]));}route.push((input.pos[a[i]].0,a[i],0,vec![]));}let mut hold=vec![];for i in (0..route.len()).rev(){route[i].2=(hold.len() as i64+1).pow(2);if route[i].1==!0{if i==0{assert!(hold.is_empty());}std::mem::swap(&mut hold,&mut route[i].3);} else{hold.push(input.pos[route[i].1].1);}}let mut dij=Dijkstra::new();let mut grid=input.is_block.clone();let mut score=a.iter().map(|&n|input.cost[n]).sum::<i64>();let mut ret=vec![];assert!(route[0].1==!0 && route[0].3.is_empty());for w in route.windows(2){let (u,v)=(w[0].0,w[1].0);let (u,v)=(input.grid.id(u),input.grid.id(v));score+=w[0].2*dij.solve(input,&grid,u,v);if w[1].1!=!0{for &n in &input.edge[w[1].1].1{grid[input.to_id[n]]=false;}}let node=dij.restore(v);for w in node.windows(2){ret.push(Move(get_dir(input.grid.pos(w[0]),input.grid.pos(w[1])) as u8));}if w[1].1==!0{assert!(input.grid[w[1].0]==Shop && grid[input.grid.id(w[1].0)]);ret.extend(w[1].3.iter().map(|&n|Buy(n)));} else{ret.push(Bom(input.pos[w[1].1].1));}}(ret,score)}const INF:i64=i64::MAX/4;const STEP:i64=1518500249; // sqrt(INF)struct Dijkstra{prev:Vec<usize>,base:i64,dist:Vec<i64>,que:(Queue<(usize,i64)>,Queue<(usize,i64)>),}impl Dijkstra{fn new()->Self{let n=(N+1)*(N+1);Self{prev:vec![!0;n],base:INF,dist:vec![INF;n],que:(Queue::new(),Queue::new()),}}fn restore(&self,mut v:usize)->Vec<usize>{let mut route=vec![];while v!=!0{route.push(v);v=self.prev[v];}route.reverse();route}// todo: 双方向化// grid: true->blockfn solve(&mut self,input:&Input,grid:&[bool],a:usize,b:usize)->i64{self.que.0.clear();self.que.1.clear();self.prev[a]=!0;self.base-=STEP;self.dist[a]=self.base-STEP;self.que.0.push_back((a,self.dist[a]));if a==b{return 0;}loop{let (v,dist);if !self.que.0.is_empty(){if !self.que.1.is_empty(){let &(_,dist0)=self.que.0.front().unwrap();let &(_,dist1)=self.que.1.front().unwrap();if dist0>dist1{(v,dist)=self.que.1.pop_front().unwrap();} else{(v,dist)=self.que.0.pop_front().unwrap();}} else{(v,dist)=self.que.0.pop_front().unwrap();}} else if !self.que.1.is_empty(){(v,dist)=self.que.1.pop_front().unwrap();} else{panic!();}if self.dist[v]!=dist{continue;}for dd in input.grid.dd{let nv=v+dd;if input.grid.is_wall(nv) || self.dist[nv]<self.base{continue;}let weight=grid[nv] as i64+1;let dist=dist+weight;self.prev[nv]=v;if nv==b{return dist-(self.base-STEP);}self.dist[nv]=dist;if weight==1{self.que.0.push_back((nv,dist));} else{self.que.1.push_back((nv,dist));}}}}}const MAX_HOLD:usize=4; // todo// 挿入dpではない// todo: 両方からDPして遅延評価するやつで高速化struct InsertionDP{ratio:Vec<f64>,dp:Vec<(f64,usize)>,next:Vec<(f64,usize)>,rest:IndexSet,t:Vec<(i64,i64,usize)>,cht:ConvexHallTrick,track:Track<usize>,last_ans:usize,}impl InsertionDP{fn new(input:&Input,a:&[usize])->Self{// let mut ratio=vec![];// let mut r=input.ratio;// for _ in 0..=a.len(){// ratio.push(r+1.);// r*=0.3;// }let ratio=vec![1.;a.len()+1]; // todo: n個終わったときの辺の重みSelf{ratio,dp:vec![(0.,!0);MAX_HOLD],next:vec![(0.,!0);MAX_HOLD],rest:IndexSet::new(input.shop.len()),t:vec![],cht:ConvexHallTrick::new(),track:Track::new(),last_ans:!0,}}// todo: 復元をしないことで高速化fn solve(&mut self,input:&Input,iter:impl Iterator<Item=usize>)->f64{self.track.clear();use std::f64::INFINITY as INF;self.dp.fill((INF,!0));self.dp[0].0=0.;self.rest.fill();let mut p0=START;// todo: 残り個数から自明に不可能なHOLDを見ないようにして高速化for (i,n) in iter.enumerate(){let p1=input.pos[n].0;let add=(p0-p1).manh() as f64*self.ratio[i];for j in 1..MAX_HOLD{let id=self.track.push(self.dp[j].1,!0);self.next[j-1]=(self.dp[j].0+add*(j+1) as f64*(j+1) as f64,id);}self.next[MAX_HOLD-1]=(INF,!0);if !self.rest.is_empty(){self.t.clear();self.t.extend(self.rest.to_slice().iter().map(|&k|((p1-input.shop[k]).manh(),(p0-input.shop[k]).manh(),k)));self.t.sort_unstable_by_key(|t|t.0);self.cht.clear();for &(a,b,k) in self.t.iter().rev(){self.cht.add(a,b,k);}for j in 0..MAX_HOLD{// prev-i間で一番近いばくだんやによるlet mul=(j as i64+2)*(j as i64+2);let (k,add)=self.cht.get(mul);let new=self.dp[0].0+add as f64*self.ratio[i];if self.next[j].0>new{let id=self.track.push(self.dp[0].1,k);self.next[j]=(new,id);}}}for &m in &input.shop_edge[n]{if self.rest.contains(m){self.rest.del(m);}}p0=p1;std::mem::swap(&mut self.dp,&mut self.next);}self.last_ans=self.dp[0].1;self.dp[0].0}fn restore(&self)->Vec<usize>{self.track.restore(self.last_ans)}}#[derive(Clone)]struct State{ans:Vec<usize>,used:Vec<bool>,cnt:Vec<usize>,set:IndexSet,cache:Vec<usize>,at:usize,is_cache:Vec<usize>,}impl State{fn new(input:&Input)->State{let mut cnt=vec![0;input.cand.len()];let mut used=vec![false;input.edge.len()];let mut ans=vec![];for i in 0..input.cand.len(){if cnt[i]!=0{continue;}let new=input.cand[i].choice();ans.push(new);assert!(!used[new]);used[new]=true;for &a in &input.edge[new].1{cnt[a]+=1;}}assert!(cnt.iter().all(|&n|0<n));State{ans,cnt,used,set:IndexSet::new(input.cand.len()),cache:vec![],at:0,is_cache:vec![0;input.cand.len()],}}fn no(&self)->i64{self.set.len() as i64}fn score(&self,input:&Input)->i64{self.ans.iter().map(|&i|input.edge[i].0).sum()}#[track_caller]fn debug(&self,input:&Input){let mut used=vec![false;input.edge.len()];let mut cnt=vec![0;input.cand.len()];for &i in &self.ans{used[i]=true;for &j in &input.edge[i].1{cnt[j]+=1;}}assert!(cnt==self.cnt);assert!(used==self.used);for i in 0..input.cand.len(){if cnt[i]==0{assert!(self.set.contains(i));} else{assert!(!self.set.contains(i));}}}fn add(&mut self,input:&Input,i:usize){for &n in &input.edge[i].1{if self.cnt[n]==0{self.set.del(n);}self.cnt[n]+=1;}}fn del(&mut self,input:&Input,i:usize){for &n in &input.edge[i].1{self.cnt[n]-=1;if self.cnt[n]==0{self.set.add(n);}}}fn del_with(&mut self,input:&Input,i:usize){self.at+=1;self.cache.clear();self.cache.extend(input.edge[i].1.iter().copied().filter(|&n|self.cnt[n]==1 && {self.is_cache[n]=self.at; true}));}fn add_with(&self,input:&Input,i:usize)->i64{-input.edge[i].1.iter().map(|&n|(self.cnt[n]==0 || self.is_cache[n]==self.at) as i64).sum::<i64>()}fn try_add(&self,input:&Input,i:usize)->i64{-input.edge[i].1.iter().map(|&n|(self.cnt[n]==0) as i64).sum::<i64>()}// todo: これの枝刈りfn try_del(&self,input:&Input,i:usize)->i64{input.edge[i].1.iter().map(|&n|(self.cnt[n]==1) as i64).sum::<i64>()}}fn trans_del(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{let old=*score as f64+state.no() as f64*k;let idx=rnd::next()%state.ans.len();let a=state.ans[idx];let diff=state.try_del(input,a);let new_score=*score-input.edge[a].0;let new=new_score as f64+(state.no()+diff) as f64*k;let diff=new-old;if diff<=add{state.del(input,a);state.used[a]=false;*score=new_score;state.ans.swap_remove(idx);true} else{false}}fn trans_add(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{let old=*score as f64+state.no() as f64*k;let a=if !state.set.is_empty(){input.cand[state.set.rand()].choice()} else{let mut a=!0;for _ in 0..10{a=rnd::next()%input.edge.len();if !state.used[a]{break;}}if a==!0{return false;}a};let diff=state.try_add(input,a);let new_score=*score+input.edge[a].0;let new=new_score as f64+(state.no()+diff) as f64*k;let diff=new-old;if diff<=add{state.add(input,a);state.used[a]=true;*score=new_score;state.ans.push(a);true} else{false}}fn trans_del_add(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{let old=*score as f64+state.no() as f64*k;let idx=rnd::next()%state.ans.len();let a=state.ans[idx];let len=state.set.len();state.del_with(input,a);if state.cache.is_empty(){state.del(input,a);state.ans.swap_remove(idx);state.used[a]=false;*score-=input.edge[a].0;return true;}let mut b=!0;for _ in 0..10{b=input.cand[state.cache.choice()].choice();if a!=b && input.edge[b].0 as f64-input.edge[a].0 as f64-(len as f64).min(0.7)*k<=add{ // todobreak;}}if b==!0{return false;}let diff=state.add_with(input,b)+state.cache.len() as i64;let new_score=*score-input.edge[a].0+input.edge[b].0;let new=new_score as f64+(state.no()+diff) as f64*k;let diff=new-old;if diff<=add{state.del(input,a);state.add(input,b);state.used[a]=false;state.used[b]=true;*score=new_score;state.ans[idx]=b;true} else{false}}fn trans(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{let t=rnd::nextf();const C:f64=0.01;if !state.ans.is_empty() && t<=C{ // todotrans_del(input,state,add,score,k)} else if state.ans.is_empty() || t<=C+C{ // todotrans_add(input,state,add,score,k)} else{trans_del_add(input,state,add,score,k)}}struct SA{start:f64,tl:f64,time:f64,heat:f64,K:f64,table:[f64;65536],state:State,}impl SA{fn new(state:State)->SA{let mut table=[0.;65536];for i in 0..65536{table[i]=((i as f64+0.5)/65536.).ln();}rnd::shuffle(&mut table);SA{start:0.,tl:0.,time:0.,heat:0.,K:1.,table,state,}}fn update(&mut self)->bool{self.time=(get_time()-self.start)/self.tl;if self.time>=1.{return false;}// todoconst T0:f64=15.;const T1:f64=0.01;let time=self.time.powf(1.5);self.heat=T0*(T1/T0).powf(time);// todoconst K0:f64=5.;const K1:f64=200.;self.K=K0+(K1-K0)*(time);true}fn solve(&mut self,input:&Input,tl:f64,k:usize)->Vec<Vec<usize>>{self.start=get_time();assert!(self.start<tl);self.tl=tl-self.start;let mut valid=0;let mut score=self.state.score(input);let mut que=std::collections::BinaryHeap::new();let mut iter=0;let mut best_score=score;let mut best=self.state.clone();while iter&255!=0 || self.update(){iter+=1;let add=-self.heat*self.table[iter&65535]; // 最小化// let add=0.;valid+=trans(input,&mut self.state,add,&mut score,self.K) as usize;if 0.1<self.time && self.state.no()==0{if que.len()<k{que.push(O(score,self.state.ans.clone()));} else if let Some(a)=que.peek(){if a.0>score{que.pop().unwrap();que.push(O(score,self.state.ans.clone()));}}if best_score>score{best_score=score;best=self.state.clone();}}}assert!(self.state.score(input)==score);self.state.debug(input);// eprintln!("score = {}",best_score);eprintln!("iter = {}",iter);// eprintln!("ratio = {:.3}",valid as f64/iter as f64);self.state=best;let mut ret=que.into_sorted_vec().into_iter().map(|t|t.1).collect::<Vec<_>>();ret.reverse();ret}}const N:usize=50;const M:usize=20;const START:P=P(0,0);#[derive(Clone,Copy,PartialEq,Eq)]enum Cell{Empty,Wall,Shop,}use Cell::*;#[derive(Clone,Copy,PartialEq,Eq)]enum Cmd{Move(u8),Buy(usize),Bom(usize),}use Cmd::*;type Grid<T>=grid_type!(T,N,N);struct Input{grid:Grid<Cell>,is_block:Vec<bool>,shop:Vec<P>,edge:Vec<(i64,Vec<usize>)>,cost:Vec<i64>,shop_edge:Vec<Vec<usize>>,pos:Vec<(P,usize)>,cand:Vec<Vec<usize>>,to_id:Vec<usize>,ratio:f64,}impl Input{fn new()->Input{let mut scan=Scanner::new();input!{scan,n:usize,m:usize,a:[Chars;n],bom:[(i64,[(i64,i64)]);m],}assert!((n,m)==(N,M));let mut grid=vec![vec![Empty;N];N];let mut shop=vec![];let mut shop_id=vec![vec![!0;N];N];for i in 0..N{for j in 0..N{grid[i][j]=match a[i][j]{'.'=>Empty,'#'=>Wall,'@'=>{shop_id[i][j]=shop.len();shop.push(P::new(i,j));Shop},_=>panic!(),};}}let grid=Grid::new(&grid,Empty);let mut edge=vec![];let mut pos=vec![];let mut id=vec![!0;grid.len()];let mut to_id=vec![];let mut is=0;let mut is_block=vec![false;grid.len()];let mut cnt=0;for i in 0..N{for j in 0..N{let p=P::new(i,j);if grid[p]!=Empty{is_block[grid.id(p)]=true;cnt+=1;id[grid.id(p)]=is;to_id.push(grid.id(p));is+=1;}}}let ratio=cnt as f64/(N*N) as f64;let mut seen=vec![0;grid.len()];let mut at=0;let mut cost=vec![];for i in 0..N{for j in 0..N{let p=P::new(i,j);for i in 0..m{at+=1;let add=bom[i].1.iter().map(|np|p+P(np.0,np.1)).filter(|&p|p.in_range(N,N)).map(|p|{seen[grid.id(p)]=at;id[grid.id(p)]}).filter(|&n|n!=!0).collect::<Vec<_>>();let mut add_cost=bom[i].0;// todoif let Some(min)=shop.iter().filter(|&&np|seen[grid.id(np)]!=at).map(|&np|(np-p).manh()).min(){add_cost+=(min as f64*4.).round() as i64;}cost.push(bom[i].0);edge.push((add_cost,add));pos.push((p,i));}}}let mut shop_edge=vec![vec![];edge.len()];for (i,t) in edge.iter().enumerate(){for &n in &t.1{let id=shop_id[grid.pos(to_id[n])];if id!=!0{shop_edge[i].push(id);}}}let mut cand=vec![vec![];is];for i in 0..edge.len(){for &n in &edge[i].1{cand[n].push(i);}}let mut t=vec![];for i in 0..is{t.clear();std::mem::swap(&mut t,&mut cand[i]);let sum=t.iter().map(|&a|edge[a].1.len() as f64/edge[a].0 as f64).sum::<f64>();for &a in &t{let ratio=edge[a].1.len() as f64/edge[a].0 as f64/sum;for _ in 0..(ratio*t.len() as f64).round() as i64{cand[i].push(a);}}}assert!(cand.iter().all(|t|!t.is_empty()));Input{grid,is_block,shop,edge,cost,shop_edge,pos,cand,to_id,ratio}}}fn write_output(ans:&[Cmd]){println!("{}",ans.len());for &c in ans{match c{Move(dir)=>println!("1 {}",DC[dir as usize]),Buy(id)=>println!("2 {}",id+1),Bom(id)=>println!("3 {}",id+1),}}}#[allow(unused)]fn get_time()->f64{static mut START:f64=-1.;let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();unsafe{if START<0.{START=time;}#[cfg(local)]{(time-START)*1.6}#[cfg(not(local))]{time-START}}}#[macro_export]macro_rules! timer{()=>{#[cfg(local)]let _timer=Timer(get_time());}}static mut TIME:f64=0.;struct Timer(f64);impl Drop for Timer{fn drop(&mut self){unsafe{TIME+=get_time()-self.0}}}#[allow(unused)]mod rnd {const C:u128=0x2360ED051FC65DA44385DF649FCCF645;static mut N:u128=C;pub fn set_seed(seed:u128){unsafe{N^=seed&!1;}}pub fn next()->usize{unsafe{let x=N;N*=C;(x as usize^(x>>64) as usize).rotate_right((x>>122) as u32)}}pub fn hash()->u64{next() as u64}pub fn nextf()->f64{unsafe{std::mem::transmute::<u64,f64>(0x3ff0000000000000|(next() as u64)>>12)-1.}}pub fn range(a:usize,b:usize)->usize{assert!(a<b);next()%(b-a)+a}pub fn range_skip(a:usize,b:usize,skip:usize)->usize{assert!(a<=skip && skip<b);let ret=range(a,b-1);ret+(skip<=ret) as usize}pub fn rangei(a:i64,b:i64)->i64{assert!(a<b);(next()%((b-a) as usize)) as i64+a}pub fn shuffle<T>(list:&mut [T]){for i in (0..list.len()).rev(){list.swap(i,next()%(i+1));}}pub fn nextl(n:usize)->usize{(next()%n).min(next()%n)}pub fn nexte(n:usize)->usize{(range(1,n+1) as f64*nextf()) as usize}}trait RandomChoice{type Output;fn choice(&self)->Self::Output;}impl<T:Copy> RandomChoice for [T]{type Output=T;fn choice(&self)->T{self[rnd::next()%self.len()]}}#[derive(Clone)]struct StaticGrid<T,const N:usize,const M:usize,const SIZE:usize>{wall:[bool;SIZE],item:[T;SIZE],dd:[usize;4],dx:[usize;8],}impl<T,const N:usize,const M:usize,const SIZE:usize> StaticGrid<T,N,M,SIZE>{// wall:=wallのときのitemfn new(grid:&Vec<Vec<T>>,wall:T)->Self where T:Copy{assert!(grid.len()==N && grid.iter().all(|t|t.len()==M));let mut item=[wall;SIZE];let mut wall=[true;SIZE];for i in 0..N{for j in 0..M{item[(i+1)*(M+1)+j+1]=grid[i][j];wall[(i+1)*(M+1)+j+1]=false;}}StaticGrid{wall,item,dd:[!0,!M,1,M+1],dx:[!0,!M-1,!M,!M+1,1,M+2,M+1,M],}}const fn len(&self)->usize{SIZE}fn id(&self,p:P)->usize{(p.0 as usize+1)*(M+1)+p.1 as usize+1}fn pos(&self,p:usize)->P{P::new(p/(M+1)-1,p%(M+1)-1)}// 壁でないものから8近傍以内のアクセスであれば正しい値が返ってくるfn is_wall(&self,p:usize)->bool{self.wall[p]}fn set_wall(&mut self,p:usize,f:bool){self.wall[p]=f;}}impl<T,const N:usize,const M:usize,const SIZE:usize> Index<usize> for StaticGrid<T,N,M,SIZE>{type Output=T;fn index(&self,n:usize)->&T{&self.item[n]}}impl<T,const N:usize,const M:usize,const SIZE:usize> IndexMut<usize> for StaticGrid<T,N,M,SIZE>{fn index_mut(&mut self,n:usize)->&mut T{&mut self.item[n]}}impl<T,const N:usize,const M:usize,const SIZE:usize> Index<P> for StaticGrid<T,N,M,SIZE>{type Output=T;fn index(&self,n:P)->&T{&self.item[self.id(n)]}}impl<T,const N:usize,const M:usize,const SIZE:usize> IndexMut<P> for StaticGrid<T,N,M,SIZE>{fn index_mut(&mut self,n:P)->&mut T{let n=self.id(n);&mut self.item[n]}}impl<T,const N:usize,const M:usize,const SIZE:usize> Index<(usize,usize)> for StaticGrid<T,N,M,SIZE>{type Output=T;fn index(&self,n:(usize,usize))->&T{&self.item[self.id(P::new(n.0,n.1))]}}impl<T,const N:usize,const M:usize,const SIZE:usize> IndexMut<(usize,usize)> for StaticGrid<T,N,M,SIZE>{fn index_mut(&mut self,n:(usize,usize))->&mut T{let n=self.id(P::new(n.0,n.1));&mut self.item[n]}}#[macro_export]macro_rules! grid_type{($t:ident,$n:expr,$m:expr)=>{StaticGrid<$t,{$n},{$m},{($m+1)*($n+2)+1}>}}#[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Debug,Default,Hash)]struct P(i64,i64);impl P{fn new(a:usize,b:usize)->P{P(a as i64,b as i64)}fn in_range(self,h:usize,w:usize)->bool{h>self.0 as usize && w>self.1 as usize}fn dot(self,a:P)->i64{self.0*a.0+self.1*a.1}fn det(self,a:P)->i64{self.0*a.1-self.1*a.0}fn manh(self)->i64{self.0.abs()+self.1.abs()}fn abs2(self)->i64{self.dot(self)}// 時計回りに90度fn rot90(self)->P{P(-self.1,self.0)}}use std::ops::*;impl Add for P{type Output=P;fn add(self,a:P)->P{P(self.0+a.0,self.1+a.1)}}impl Sub for P{type Output=P;fn sub(self,a:P)->P{P(self.0-a.0,self.1-a.1)}}impl Mul<i64> for P{type Output=P;fn mul(self,a:i64)->P{P(self.0*a,self.1*a)}}impl Div<i64> for P{type Output=P;fn div(self,a:i64)->P{P(self.0/a,self.1/a)}}impl Neg for P{type Output=P;fn neg(self)->P{P(-self.0,-self.1)}}impl AddAssign for P{fn add_assign(&mut self,a:P){*self=*self+a;}}impl SubAssign for P{fn sub_assign(&mut self,a:P){*self=*self-a;}}impl MulAssign<i64> for P{fn mul_assign(&mut self,a:i64){*self=*self*a;}}impl DivAssign<i64> for P{fn div_assign(&mut self,a:i64){*self=*self/a;}}impl<T:Index<usize>> Index<P> for [T]{type Output=T::Output;fn index(&self,idx:P)->&T::Output{&self[idx.0 as usize][idx.1 as usize]}}impl<T:IndexMut<usize>> IndexMut<P> for [T]{fn index_mut(&mut self,idx:P)->&mut T::Output{&mut self[idx.0 as usize][idx.1 as usize]}}impl<T:Index<usize>> Index<P> for Vec<T>{type Output=T::Output;fn index(&self,idx:P)->&T::Output{&self[idx.0 as usize][idx.1 as usize]}}impl<T:IndexMut<usize>> IndexMut<P> for Vec<T>{fn index_mut(&mut self,idx:P)->&mut T::Output{&mut self[idx.0 as usize][idx.1 as usize]}}const DD:[P;4]=[P(0,-1),P(-1,0),P(0,1),P(1,0)];const DC:[char;4]=['L','U','R','D'];fn get_dir(a:P,b:P)->usize{(0..4).find(|&i|DD[i]==b-a).unwrap()}struct Scanner{stack:std::str::SplitAsciiWhitespace<'static>}impl Scanner{fn new()->Self{use std::io::Read;let mut tmp=String::new();std::io::stdin().read_to_string(&mut tmp).unwrap();Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}}fn read<T:std::str::FromStr>(&mut self)->T{self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))}}#[macro_export]macro_rules! input{($scan:expr $(,)?)=>{};($scan:expr, mut $name:ident:$t:tt $($rest:tt)*)=>{let mut $name=read_value!($scan,$t);input!{$scan $($rest)*}};($scan:expr, $name:ident:$t:tt $($rest:tt)*)=>{let $name=read_value!($scan,$t);input!{$scan $($rest)*}};}#[macro_export]macro_rules! read_value{($scan:expr, ($($t:tt),*))=>{($(read_value!($scan, $t)),*)};($scan:expr, [$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()};($scan:expr, [$t:tt])=>{(0..$scan.read()).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()};($scan:expr, Chars)=>{read_value!($scan,String).chars().collect::<Vec<char>>()};($scan:expr, Usize1)=>{read_value!($scan,usize)-1};($scan:expr, $t:ty)=>{$scan.read::<$t>()};}#[derive(Clone)]struct IndexSet{pos:Vec<usize>,que:Vec<usize>,len:usize}impl IndexSet{fn new(n:usize)->Self{IndexSet{pos:(0..n).collect(),que:(0..n).collect(),len:0}}fn add(&mut self,a:usize){let p=self.pos[a];assert!(self.len<=p);self.que.swap(p,self.len);self.pos.swap(a,self.que[p]);self.len+=1;}fn del(&mut self,a:usize){let p=self.pos[a];assert!(p<self.len);self.que.swap(p,self.len-1);self.pos.swap(a,self.que[p]);self.len-=1;}fn rand(&self)->usize{self.que[rnd::next()%self.len]}fn to_slice(&self)->&[usize]{&self.que[..self.len]}fn contains(&self,v:usize)->bool{self.pos[v]<self.len}fn is_empty(&self)->bool{self.len==0}fn len(&self)->usize{self.len}fn clear(&mut self){self.len=0;}fn fill(&mut self){self.len=self.pos.len();}}impl std::cmp::PartialEq for IndexSet{fn eq(&self,a:&IndexSet)->bool{self.pos.len()==a.pos.len() && self.len==a.len&& self.to_slice().iter().all(|&n|a.contains(n))}}struct Queue<T>{data:Vec<T>,head:usize,}impl<T> Queue<T>{fn new()->Self{Queue{data:vec![],head:0,}}fn clear(&mut self){self.data.clear();self.head=0;}fn is_empty(&self)->bool{self.head==self.data.len()}fn len(&self)->usize{self.data.len()-self.head}fn push_back(&mut self,v:T){self.data.push(v);}fn pop_front(&mut self)->Option<T> where T:Copy{if self.head==self.data.len(){None} else{self.head+=1;Some(self.data[self.head-1])}}fn front(&self)->Option<&T>{if self.is_empty(){None} else{Some(&self.data[self.head])}}fn to_slice(&self)->&[T]{&self.data[self.head..]}}impl<T> Deref for Queue<T>{type Target=[T];fn deref(&self)->&[T]{&self.data[self.head..]}}impl<T> DerefMut for Queue<T>{fn deref_mut(&mut self)->&mut [T]{&mut self.data[self.head..]}}impl<T> Index<usize> for Queue<T>{type Output=T;fn index(&self,n:usize)->&T{let idx=self.head+n;assert!(self.head<=idx);&self.data[idx]}}impl<T> IndexMut<usize> for Queue<T>{fn index_mut(&mut self,n:usize)->&mut T{let idx=self.head+n;assert!(self.head<=idx);&mut self.data[idx]}}// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254// kickしてから2-opt,3-optで局所最適にするのを1近傍とした山登り// 枝刈りをそれなりに入れてるfn get_score(dist:&Vec<Vec<i64>>,route:&[usize])->i64{route.windows(2).map(|w|dist[w[0]][w[1]]).sum()}// mv: (i, dir)fn apply_move<const K:usize>(tour:&mut [usize],idx:&mut [usize],mv:&[(usize,usize);K],BF:&mut Vec<usize>){let mut ids=[!0;K];let mut it=0..;ids.fill_with(||it.next().unwrap());ids.sort_unstable_by_key(|&i|mv[i].0);let mut order=[0;K];for i in 0..K{order[ids[i]]=i;}let mut i=ids[0];let mut dir=0;BF.clear();loop {let (j,rev)=if dir==mv[i].1{((i+1)%K,0)}else{((i+K-1)%K,1)};if mv[j].1==rev{if order[j]==K-1{break;}i=ids[order[j]+1];dir=0;BF.extend_from_slice(&tour[mv[j].0+1..mv[i].0+1]);}else{i=ids[order[j]-1];dir=1;BF.extend(tour[mv[i].0+1..mv[j].0+1].iter().rev().cloned());}}assert_eq!(BF.len(),mv[ids[K-1]].0-mv[ids[0]].0);tour[mv[ids[0]].0+1..mv[ids[K-1]].0+1].copy_from_slice(&BF);for i in mv[ids[0]].0+1..mv[ids[K-1]].0+1{idx[tour[i]]=i;}}const FEASIBLE3:[bool;64]=[false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false];// 一番近いやつを追加していくfn solve_tsp_greedy(dist:&Vec<Vec<i64>>,start:usize)->Vec<usize>{let mut ret=vec![start];let mut rest:Vec<_>=(0..dist.len()).filter(|&i|i!=start).collect();while !rest.is_empty(){let last=*ret.last().unwrap();let idx=(0..rest.len()).min_by_key(|&i|dist[last][rest[i]]).unwrap();ret.push(rest.swap_remove(idx));}ret.push(start);ret}// routeは初期解を指定可能fn solve_tsp_ils(dist:&Vec<Vec<i64>>,mut route:Vec<usize>)->Vec<usize>{let n=dist.len();assert_eq!(n,route.len()-1);let mut f=vec![vec![];n];for i in 0..n{for j in 0..n{if i!=j{f[i].push((dist[i][j],j));}}f[i].sort_unstable_by_key(|t|t.0);}let mut idx=vec![!0;n];let (mut min_score,mut best)=(get_score(&dist,&route),route.clone());let mut BF=vec![];for _ in 0..5{ // todolet mut cost=get_score(&dist,&route);for i in 0..n{idx[route[i]]=i;}loop {let mut ok=false;for i in 0..n{for di in 0..2{'a: for &(ij,vj) in &f[route[i+di]]{if dist[route[i]][route[i+1]]-ij<=0{break;}for dj in 0..2{let j=if idx[vj]==0 && dj==0{n-1} else {idx[vj]-1+dj};let gain=dist[route[i]][route[i+1]]-ij+dist[route[j]][route[j+1]];let diff=gain-dist[route[j+dj]][route[i+1-di]];if di!=dj && diff>0{cost-=diff;apply_move(&mut route,&mut idx,&[(i,di),(j,dj)],&mut BF);ok=true;break 'a;}for &(jk,vk) in &f[route[j+dj]]{if gain-jk<=0{break;}for dk in 0..2{let k=if idx[vk]==0 && dk==0{n-1} else {idx[vk]-1+dk};if i==k || j==k{continue;}let diff=gain-jk+dist[route[k]][route[k+1]]-dist[route[k+dk]][route[i+1-di]];if diff>0{let mask=((i<j) as usize)<<5 | ((i<k) as usize)<<4 | ((j<k) as usize)<<3 | di<<2 | dj<<1 | dk;if FEASIBLE3[mask]{cost-=diff;apply_move(&mut route,&mut idx,&[(i,di),(j,dj),(k,dk)],&mut BF);ok=true;break 'a;}}}}}}}}if !ok{break;}}if min_score>cost{min_score=cost;best.clear();best.extend(&route);} else{route.clear();route.extend(&best);}if rnd::next()&1==0{// double bridgelet mut is=[!0;4];loop{is.fill_with(||rnd::next()%n+1);is.sort_unstable();if is[0]!=is[1] && is[1]!=is[2] && is[2]!=is[3]{break;}}BF.clear();let it=route[is[2]..is[3]].iter().chain(&route[is[1]..is[2]]).chain(&route[is[0]..is[1]]);BF.extend(it.cloned());route[is[0]..is[3]].copy_from_slice(&BF);}else{for _ in 0..6{loop{let i=rnd::next()%(n-1);let j=rnd::next()%(n-1);if i<j && j-i<n-2{route[i+1..j].reverse();break;}}}}}best}struct ConvexHallTrick(Vec<((i64,i64),usize)>,usize);impl ConvexHallTrick{fn new()->Self{Self(vec![],0)}fn clear(&mut self){self.0.clear();self.1=0;}// y=ax+bを追加// aが単調減少の必要があるfn add(&mut self,a:i64,b:i64,id:usize){loop{let len=self.0.len();if len<2 || !check(self.0[len-2].0,self.0[len-1].0,(a,b)){break;}self.0.pop().unwrap();}self.0.push(((a,b),id));}fn f(&self,i:usize,x:i64)->i64{self.0[i].0.0*x+self.0[i].0.1}// f(x)の最小値// xは単調増加の必要があるfn get(&mut self,x:i64)->(usize,i64){while self.0.len()-self.1>=2 && self.f(self.1,x)>=self.f(self.1+1,x){self.1+=1;}(self.0[self.1].1,self.f(self.1,x))}}fn check(l0:(i64,i64),l1:(i64,i64),l2:(i64,i64))->bool{(l1.0-l0.0)*(l2.1-l1.1)>=(l1.1-l0.1)*(l2.0-l1.0)}struct Track<T>(Vec<(usize,T)>);impl<T> Track<T>{fn new()->Self{Track(vec![])}fn clear(&mut self){self.0.clear();}fn push(&mut self,prev:usize,v:T)->usize{self.0.push((prev,v));self.0.len()-1}fn restore(&self,mut idx:usize)->Vec<T> where T:Clone{let mut ret=vec![];while idx!=!0{let (prev,v)=self.0[idx].clone();ret.push(v);idx=prev;}ret.reverse();ret}}impl<T> Index<usize> for Track<T>{type Output=T;fn index(&self,idx:usize)->&T{&self.0[idx].1}}struct O<T:PartialOrd,U>(T,U);impl<T:PartialOrd,U> PartialEq for O<T,U>{fn eq(&self,a:&Self)->bool{self.0==a.0}}impl<T:PartialOrd,U> PartialOrd for O<T,U>{fn partial_cmp(&self,a:&Self)->Option<std::cmp::Ordering>{self.0.partial_cmp(&a.0)}}impl<T:PartialOrd,U> Eq for O<T,U>{}impl<T:PartialOrd,U> Ord for O<T,U>{fn cmp(&self,a:&Self)->std::cmp::Ordering{self.0.partial_cmp(&a.0).unwrap()}}fn multi_start_iter(mut n:usize,tl:f64)->impl Iterator<Item=f64>{std::iter::from_fn(move||{if n==0{None} else{let time=get_time();let ret=Some((tl-time)/n as f64+time);n-=1;ret}})}#[macro_export] macro_rules! eprint{($($_:tt)*)=>{}}#[macro_export] macro_rules! eprintln{($($_:tt)*)=>{}}#[macro_export] macro_rules! assert{($($_:tt)*)=>{}}#[macro_export] macro_rules! assert_eq{($($_:tt)*)=>{}}#[macro_export] macro_rules! assert_ne{($($_:tt)*)=>{}}