#[allow(unused_imports)] use std::thread::JoinHandle; #[allow(unused_imports)] use std::time::{Duration, Instant}; #[allow(unused_imports)] use std::io::Write; #[allow(unused_imports)] use std::fs::File; #[allow(unused_imports)] use std::process::Command; #[allow(unused_imports)] use std::cmp; #[allow(unused_imports)] use std::num::Wrapping; use std::collections::BinaryHeap; fn main() { let start = Instant::now(); let mut state=State::new(); let mut rand=Rand::new(); const TL: f64 = 2.3; const T0: f64 = 90000000.0; const T1: f64 = 600000.0; let mut tt = T0; let mut dd; let mut ms; let mut cnt=0; loop { cnt+=1; if cnt%100==0 { dd=Instant::now().duration_since(start); ms=dd.as_secs() as f64 + dd.subsec_nanos() as f64 * 1e-9; if ms > TL { break; } let tk = ms / TL; tt = T0.powf(1.0 - tk) * T1.powf(tk); } let rn=rand.get(10); if rn==0 || state.ac.len()<2 { let yk=rand.get(State::N); let xk=rand.get(State::N); let ik=rand.get(State::M); let mtk=state.apr(yk, xk, ik); let f1=f64::exp((mtk - state.pt) as f64 / tt); let f2=rand.get2() as f64/usize::MAX as f64; if mtk>state.pt || f2state.pt || f2state.pt || f2>, ca:Vec>, pt:i64, ac:Vec<(usize,usize,usize)>, bs:Vec<(usize,usize)>, boms:Vec, pa:[i64;Self::PM], fb:Vec>, fbn:i32, fh:Vec>, } impl State { const N: usize = 50; const M: usize = 20; const PM: usize = 20; const BB: u8 = '@' as u8 ; const BN: u8 = '.' as u8 ; const YH:[usize;4] = [!0,0,1,0]; const XH:[usize;4] = [0,1,0,!0]; const CH:[char;4] = ['U','R','D','L']; pub fn new() -> Self { getline(); let mut pa=[0_i64;Self::PM]; pa[1]=10000000; for i in 2..pa.len() {pa[i]=pa[i-1]-140000;} let mut hc=0; let mut bm=Vec::with_capacity(Self::N); let mut bs: Vec<(usize, usize)>=Vec::new(); for i in 0..Self::N { let s=getline(); let aa=s.as_bytes(); bm.push(Vec::with_capacity(Self::N)); for j in 0..Self::N { if aa[j]==Self::BB { hc+=1; bs.push((i,j)); } bm[i].push(aa[j]); } } let mut boms:Vec=Vec::with_capacity(State::M); for i in 0..State::M {boms.push(Bom::new(i));} let mut ac=Vec::new(); ac.push((0,0,!0)); Self { hcb:hc, bm:bm, ca:vec![vec![0;Self::N];Self::N], pt:0, ac:ac, boms:boms, pa:pa, bs:bs, fb:vec![vec![0;Self::N];Self::N], fbn:0, fh:vec![vec![0;Self::N];Self::N], } } pub fn tsp(&mut self) { let mut bo=true; while bo { bo=false; for i in 1..self.ac.len() { for j in (i+1)..self.ac.len() { let c1=self.tspc(i-1,i)+self.tspc(j,j+1); let c2=self.tspc(i-1,j)+self.tspc(i,j+1); if c2 usize { if i1==self.ac.len() || i2==self.ac.len() {return 0;} let p1=if self.ac[i1].0 > self.ac[i2].0 {self.ac[i1].0-self.ac[i2].0} else {self.ac[i2].0-self.ac[i1].0}; let p2=if self.ac[i1].1 > self.ac[i2].1 {self.ac[i1].1-self.ac[i2].1} else {self.ac[i2].1-self.ac[i1].1}; return p1+p2; } pub fn out(&mut self) -> String { let mut ny=0; let mut nx=0; let mut b=0; let mut ans=Vec::new(); for i in 1..self.ac.len() { if self.hcb>0 { let mut bb=1; if self.fbc(self.ac[i].0,self.ac[i].1,self.ac[i].2) { bb=(self.ac.len()-i) as i32; } let mut ee=i32::MAX; let mut ik=!0; for j in 0..self.bs.len() { if self.bm[self.bs[j].0][self.bs[j].1]!=Self::BB {continue;} let mut ek=self.di2(ny,nx,self.bs[j].0,self.bs[j].1,b); ek+=self.di2(self.bs[j].0,self.bs[j].1,self.ac[i].0,self.ac[i].1,b+bb); if ek>().join("\n")); return sa; } pub fn di(&mut self,ys:usize,xs:usize,yg:usize,xg:usize,bn:i32) -> Vec { self.fbn+=1; let mut pq = BinaryHeap::new(); let mut vec=Vec::new(); pq.push(Dt::new(0,ys,xs,!0)); while pq.len()>0 { let e=pq.pop().unwrap(); if self.fb[e.y][e.x]==self.fbn {continue}; self.fb[e.y][e.x]=self.fbn; self.fh[e.y][e.x]=e.h; if e.y==yg && e.x==xg { let mut zy=e.y; let mut zx=e.x; while zy!=ys || zx!=xs { vec.push(self.fh[zy][zx]); let ky=zy.wrapping_add(Self::YH[self.fh[zy][zx]^2]); let kx=zx.wrapping_add(Self::XH[self.fh[zy][zx]^2]); zy=ky; zx=kx; } vec.reverse(); break; } for i in 0..4 { let yk=e.y.wrapping_add(Self::YH[i]); let xk=e.x.wrapping_add(Self::XH[i]); if yk>=Self::N || xk>=Self::N {continue;} if self.fb[yk][xk]==self.fbn {continue;} if self.bm[yk][xk]==Self::BN { pq.push(Dt::new(e.n+(bn+1)*(bn+1),yk,xk,i)); } else { pq.push(Dt::new(e.n+(bn+1)*(bn+1)*2,yk,xk,i)); } } } return vec; } pub fn di2(&mut self,ys:usize,xs:usize,yg:usize,xg:usize,bn:i32) -> i32 { self.fbn+=1; let mut pq = BinaryHeap::new(); pq.push(Dt::new(0,ys,xs,!0)); let mut aaa=0; while pq.len()>0 { let e=pq.pop().unwrap(); if self.fb[e.y][e.x]==self.fbn {continue}; self.fb[e.y][e.x]=self.fbn; if e.y==yg && e.x==xg { aaa=e.n; break; } for i in 0..4 { let yk=e.y.wrapping_add(Self::YH[i]); let xk=e.x.wrapping_add(Self::XH[i]); if yk>=Self::N || xk>=Self::N {continue;} if self.fb[yk][xk]==self.fbn {continue;} if self.bm[yk][xk]==Self::BN { pq.push(Dt::new(e.n+(bn+1)*(bn+1),yk,xk,i)); } else { pq.push(Dt::new(e.n+(bn+1)*(bn+1)*2,yk,xk,i)); } } } return aaa; } pub fn fbc(&mut self,y:usize,x:usize,ik:usize) -> bool { let bom=&self.boms[ik]; let mut bk=0; for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=y.wrapping_add(o.0); let xk=x.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BB { bk+=1; } } return bk==self.hcb; } pub fn ex(&mut self,y:usize,x:usize,ik:usize) { let bom=&self.boms[ik]; for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=y.wrapping_add(o.0); let xk=x.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BB {self.hcb-=1;} self.bm[yk][xk]=Self::BN; } } pub fn apr(&self,y:usize,x:usize,ik:usize) -> i64 { let bom=&self.boms[ik]; let mut ptk=self.pt-bom.c; for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=y.wrapping_add(o.0); let xk=x.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BN {continue;} let mut d=cmp::min(self.ca[yk][xk],self.pa.len()-1); ptk-=self.pa[d]; d=cmp::min(d+1,self.pa.len()-1); ptk+=self.pa[d]; } return ptk; } pub fn dpr(&self,ik:usize) -> i64 { let y=self.ac[ik].0; let x=self.ac[ik].1; let bom=&self.boms[self.ac[ik].2]; let mut ptk=self.pt+bom.c; for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=y.wrapping_add(o.0); let xk=x.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BN {continue;} let mut d=cmp::min(self.ca[yk][xk],self.pa.len()-1); ptk-=self.pa[d]; d=cmp::min(d-1,self.pa.len()-1); ptk+=self.pa[d]; } return ptk; } pub fn adpr(&self,y:usize,x:usize,ik:usize,jk:usize) -> i64 { let yd=self.ac[jk].0; let xd=self.ac[jk].1; let bom=&self.boms[self.ac[jk].2]; let mut ptk=self.pt+bom.c; for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=yd.wrapping_add(o.0); let xk=xd.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BN {continue;} let mut d=cmp::min(self.ca[yk][xk],self.pa.len()-1); ptk-=self.pa[d]; d=cmp::min(d-1,self.pa.len()-1); ptk+=self.pa[d]; } let bom=&self.boms[ik]; ptk-=bom.c; for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=y.wrapping_add(o.0); let xk=x.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BN {continue;} let mut d=cmp::min(self.ca[yk][xk],self.pa.len()-1); ptk-=self.pa[d]; d=cmp::min(d+1,self.pa.len()-1); ptk+=self.pa[d]; } return ptk; } pub fn add(&mut self,y:usize,x:usize,ik:usize,ptk:i64) { let bom=&self.boms[ik]; self.ac.push((y,x,bom.i)); for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=y.wrapping_add(o.0); let xk=x.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BN {continue;} self.ca[yk][xk]+=1; } self.pt=ptk; } pub fn sub(&mut self,ik:usize,ptk:i64) { let ll=self.ac.len()-1; self.ac.swap(ik, ll); let acd=self.ac[ll]; let y=acd.0; let x=acd.1; let bom=&self.boms[acd.2]; for i in 0..bom.vec.len() { let o=bom.vec[i]; let yk=y.wrapping_add(o.0); let xk=x.wrapping_add(o.1); if yk>=Self::N || xk>=Self::N {continue;} if self.bm[yk][xk]==Self::BN {continue;} self.ca[yk][xk]-=1; } self.ac.pop(); self.pt=ptk; } } #[derive(Debug, PartialEq, Eq)] pub struct Dt { n:i32, y:usize, x:usize, h:usize } impl Dt { pub fn new(n:i32,y:usize,x:usize,h:usize) -> Self { Self {n:n,y:y,x:x,h:h} } } impl Ord for Dt { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.n.cmp(&other.n).reverse() } } impl PartialOrd for Dt { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } pub struct Bom { i: usize, c: i64, l: usize, vec:Vec<(usize,usize)> } impl Bom { pub fn new(i:usize) -> Self { let s=getline(); let a:Vec<_>=s.trim().split(' ').collect(); let c:i64=a[0].parse().unwrap(); let l:usize=a[1].parse().unwrap(); let mut vec= Vec::with_capacity(l); for _ in 0..l { let s=getline(); let a:Vec<_>=s.trim().split(' ').collect(); let y:i32=a[0].parse().unwrap(); let x:i32=a[1].parse().unwrap(); vec.push((y as usize,x as usize)); } Self { i:i, c:c, l:l, vec:vec, } } } fn getline() -> String{ let mut __ret=String::new(); std::io::stdin().read_line(&mut __ret).ok(); return __ret; } pub struct Rand { hsx:usize, hsy:usize, hsz:usize, hsw:usize, } impl Rand { pub fn new() -> Self { Self { hsx:15733141579192332639, hsy:2335109221169850231, hsz:11649577722817784940, hsw:Instant::now().elapsed().as_nanos() as usize, } } pub fn get2(&mut self) -> usize{ let t = self.hsx^(self.hsx<<11); self.hsx=self.hsy; self.hsy=self.hsz; self.hsz=self.hsw; self.hsw=self.hsw^(self.hsw>>19)^t^(t>>8); return self.hsw; } pub fn get(&mut self,m:usize) -> usize{ let t = self.hsx^(self.hsx<<11); self.hsx=self.hsy; self.hsy=self.hsz; self.hsz=self.hsw; self.hsw=self.hsw^(self.hsw>>19)^t^(t>>8); return self.hsw%m; } }