結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 rhoo
|
| 提出日時 | 2023-11-19 16:36:51 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2,970 ms / 3,000 ms |
| コード長 | 42,853 bytes |
| コンパイル時間 | 6,606 ms |
| コンパイル使用メモリ | 230,700 KB |
| 実行使用メモリ | 171,776 KB |
| スコア | 2,908,857,427 |
| 最終ジャッジ日時 | 2023-11-19 16:39:34 |
| 合計ジャッジ時間 | 163,037 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,969 ms
152,960 KB |
| testcase_01 | AC | 2,967 ms
149,376 KB |
| testcase_02 | AC | 2,970 ms
171,776 KB |
| testcase_03 | AC | 2,965 ms
113,920 KB |
| testcase_04 | AC | 2,967 ms
150,528 KB |
| testcase_05 | AC | 2,966 ms
131,584 KB |
| testcase_06 | AC | 2,966 ms
111,360 KB |
| testcase_07 | AC | 2,968 ms
152,960 KB |
| testcase_08 | AC | 2,966 ms
134,784 KB |
| testcase_09 | AC | 2,968 ms
141,824 KB |
| testcase_10 | AC | 2,964 ms
105,728 KB |
| testcase_11 | AC | 2,966 ms
135,552 KB |
| testcase_12 | AC | 2,968 ms
131,712 KB |
| testcase_13 | AC | 2,966 ms
129,408 KB |
| testcase_14 | AC | 2,967 ms
137,728 KB |
| testcase_15 | AC | 2,964 ms
107,008 KB |
| testcase_16 | AC | 2,967 ms
134,016 KB |
| testcase_17 | AC | 2,967 ms
142,464 KB |
| testcase_18 | AC | 2,966 ms
127,360 KB |
| testcase_19 | AC | 2,967 ms
134,912 KB |
| testcase_20 | AC | 2,968 ms
139,520 KB |
| testcase_21 | AC | 2,968 ms
143,872 KB |
| testcase_22 | AC | 2,964 ms
126,976 KB |
| testcase_23 | AC | 2,967 ms
137,600 KB |
| testcase_24 | AC | 2,970 ms
170,496 KB |
| testcase_25 | AC | 2,967 ms
132,096 KB |
| testcase_26 | AC | 2,968 ms
145,408 KB |
| testcase_27 | AC | 2,968 ms
155,776 KB |
| testcase_28 | AC | 2,966 ms
121,600 KB |
| testcase_29 | AC | 2,966 ms
121,600 KB |
| testcase_30 | AC | 2,966 ms
120,448 KB |
| testcase_31 | AC | 2,965 ms
108,672 KB |
| testcase_32 | AC | 2,966 ms
120,832 KB |
| testcase_33 | AC | 2,968 ms
156,544 KB |
| testcase_34 | AC | 2,967 ms
136,960 KB |
| testcase_35 | AC | 2,966 ms
128,000 KB |
| testcase_36 | AC | 2,965 ms
122,368 KB |
| testcase_37 | AC | 2,965 ms
107,392 KB |
| testcase_38 | AC | 2,964 ms
92,672 KB |
| testcase_39 | AC | 2,968 ms
168,832 KB |
| testcase_40 | AC | 2,968 ms
146,304 KB |
| testcase_41 | AC | 2,969 ms
158,976 KB |
| testcase_42 | AC | 2,966 ms
124,672 KB |
| testcase_43 | AC | 2,967 ms
166,272 KB |
| testcase_44 | AC | 2,968 ms
135,040 KB |
| testcase_45 | AC | 2,965 ms
113,920 KB |
| testcase_46 | AC | 2,967 ms
142,592 KB |
| testcase_47 | AC | 2,967 ms
140,032 KB |
| testcase_48 | AC | 2,967 ms
130,176 KB |
| testcase_49 | AC | 2,969 ms
147,200 KB |
コンパイルメッセージ
warning: variable `valid` is assigned to, but never used
--> Main.rs:687:17
|
687 | let mut valid=0;
| ^^^^^
|
= note: consider using `_valid` instead
= note: `#[warn(unused_variables)]` on by default
warning: constant `M` is never used
--> Main.rs:728:7
|
728 | const M:usize=20;
| ^
|
= note: `#[warn(dead_code)]` on by default
warning: field `ratio` is never read
--> Main.rs:767:5
|
757 | struct Input{
| ----- field in this struct
...
767 | ratio:f64,
| ^^^^^
warning: field `dx` is never read
--> Main.rs:1019:5
|
1015 | struct StaticGrid<T,const N:usize,const M:usize,const SIZE:usize>{
| ---------- field in this struct
...
1019 | 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:1058:8
|
1021 | impl<T,const N:usize,const M:usize,const SIZE:usize> StaticGrid<T,N,M,SIZE>{
| --------------------------------------------------------------------------- method in this implementation
...
1058 | fn set_wall(&mut self,p:usize,f:bool){
| ^^^^^^^^
warning: methods `dot`, `det`, `abs2`, and `rot90` are never used
--> Main.rs:1119:8
|
1110 | impl P{
| ------ methods in this implementation
...
1119 | fn dot(self,a:P)->i64{
| ^^^
...
1123 | fn det(self,a:P)->i64{
| ^^^
...
1131 | fn abs2(self)->i64{
| ^^^^
...
1136 | fn rot90(self)->P{
| ^^^^^
warning: method `clear` is never used
--> Main.rs:1333:8
|
1286 | impl IndexSet{
| ------------- method in this implementation
...
1333 | fn clear(&mut self){
| ^^^^^
warning: methods `len` and `to_slice` are never used
--> Main.rs:1372:8
|
1355 | 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,15); // 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().rev()){
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()
}
};
while get_time()<=tl{ // todo
let (i,j)=(0..10) // todo
.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();
// todo: 焼きなまし?
let new=DP.solve(input,a[..i].iter().chain(a[i..j].iter().rev()).chain(a[j..].iter()).copied());
if score>=new{
score=new;
a[i..j].reverse();
}
}
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->block
fn 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=5; // 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.5)*k<=add{ // todo
break;
}
}
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{ // todo
trans_del(input,state,add,score,k)
} else if state.ans.is_empty() || t<=C+C{ // todo
trans_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;
}
// todo
const T0:f64=15.;
const T1:f64=0.01;
let time=self.time.powf(1.5);
self.heat=T0*(T1/T0).powf(time);
// todo
const K0:f64=20.;
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;
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()));
}
}
}
}
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);
que.into_sorted_vec().into_iter().map(|t|t.1).collect()
}
}
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;
// todo
if 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のときのitem
fn 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{ // todo
let 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 bridge
let 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]#[cfg(not(local))]macro_rules! eprint{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! eprintln{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! assert{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! assert_eq{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! assert_ne{($($_:tt)*)=>{}}