結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2023-11-19 17:20:43 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2,720 ms / 3,000 ms |
| コード長 | 12,242 bytes |
| コンパイル時間 | 2,151 ms |
| コンパイル使用メモリ | 208,040 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 1,939,356,797 |
| 最終ジャッジ日時 | 2023-11-19 17:23:03 |
| 合計ジャッジ時間 | 139,200 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
warning: field `l` is never read
--> Main.rs:427:2
|
424 | pub struct Bom {
| --- field in this struct
...
427 | l: usize,
| ^
|
= note: `#[warn(dead_code)]` on by default
warning: 1 warning emitted
ソースコード
#[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 || f2<f1 {state.add(yk,xk,ik,mtk);}}else if rn<5 {let ik=rand.get(state.ac.len()-1)+1;let mtk=state.dpr(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 || f2<f1 {state.sub(ik,mtk);}}else {let yk=rand.get(State::N);let xk=rand.get(State::N);let ik=rand.get(State::M);let jk=rand.get(state.ac.len()-1)+1;let mtk=state.adpr(yk, xk, ik, jk);let f1=f64::exp((mtk - state.pt) as f64 / tt);let f2=rand.get2() as f64/usize::MAX as f64;if mtk>state.pt || f2<f1 {state.sub(jk,mtk);state.add(yk,xk,ik,mtk);}}}state.tsp();let ans=state.out();println!("{}",ans);}pub struct State {hcb:usize,bm:Vec<Vec<u8>>,ca:Vec<Vec<usize>>,pt:i64,ac:Vec<(usize,usize,usize)>,bs:Vec<(usize,usize)>,boms:Vec<Bom>,pa:[i64;Self::PM],fb:Vec<Vec<i32>>,fbn:i32,fh:Vec<Vec<usize>>,}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<Bom>=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<c1 {let mut k=i;let mut l=j;while k<l {self.ac.swap(k, l);k+=1;l-=1;}bo=true;}}}}}pub fn tspc(&self,i1:usize,i2:usize) -> 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<ee {ee=ek;ik=j;}}let e=self.di(ny,nx,self.bs[ik].0,self.bs[ik].1,b);for j in 0..e.len() {ans.push(format!("1 {}",Self::CH[e[j]]));}if bb==1 {ans.push(format!("2 {}",self.ac[i].2+1));}else {for j in i..self.ac.len() {ans.push(format!("2 {}",self.ac[j].2+1));}}b+=bb;let e=self.di(self.bs[ik].0,self.bs[ik].1,self.ac[i].0,self.ac[i].1,b);for j in 0..e.len() {ans.push(format!("1 {}",Self::CH[e[j]]));}}else {let e=self.di(ny,nx,self.ac[i].0,self.ac[i].1,b);for j in 0..e.len() {ans.push(format!("1 {}",Self::CH[e[j]]));}}ny=self.ac[i].0;nx=self.ac[i].1;ans.push(format!("3 {}",self.ac[i].2+1));self.ex(self.ac[i].0,self.ac[i].1,self.ac[i].2);b-=1;}let sa=format!("{}\n{}",ans.len(),ans.iter().map(|x| x.to_string()).collect::<Vec<String>>().join("\n"));return sa;}pub fn di(&mut self,ys:usize,xs:usize,yg:usize,xg:usize,bn:i32) -> Vec<usize> {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<std::cmp::Ordering> {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;}}