#929636 (Rust) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	fgwiebfaoish
提出日時	2023-11-19 17:20:43
言語	Rust (1.77.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
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,648 ms 6,676 KB
testcase_01	AC	2,580 ms 6,676 KB
testcase_02	AC	2,493 ms 6,676 KB
testcase_03	AC	2,620 ms 6,676 KB
testcase_04	AC	2,527 ms 6,676 KB
testcase_05	AC	2,471 ms 6,676 KB
testcase_06	AC	2,610 ms 6,676 KB
testcase_07	AC	2,700 ms 6,676 KB
testcase_08	AC	2,638 ms 6,676 KB
testcase_09	AC	2,532 ms 6,676 KB
testcase_10	AC	2,487 ms 6,676 KB
testcase_11	AC	2,565 ms 6,676 KB
testcase_12	AC	2,524 ms 6,676 KB
testcase_13	AC	2,428 ms 6,676 KB
testcase_14	AC	2,600 ms 6,676 KB
testcase_15	AC	2,452 ms 6,676 KB
testcase_16	AC	2,477 ms 6,676 KB
testcase_17	AC	2,511 ms 6,676 KB
testcase_18	AC	2,720 ms 6,676 KB
testcase_19	AC	2,566 ms 6,676 KB
testcase_20	AC	2,498 ms 6,676 KB
testcase_21	AC	2,625 ms 6,676 KB
testcase_22	AC	2,531 ms 6,676 KB
testcase_23	AC	2,515 ms 6,676 KB
testcase_24	AC	2,589 ms 6,676 KB
testcase_25	AC	2,550 ms 6,676 KB
testcase_26	AC	2,564 ms 6,676 KB
testcase_27	AC	2,619 ms 6,676 KB
testcase_28	AC	2,404 ms 6,676 KB
testcase_29	AC	2,480 ms 6,676 KB
testcase_30	AC	2,593 ms 6,676 KB
testcase_31	AC	2,482 ms 6,676 KB
testcase_32	AC	2,605 ms 6,676 KB
testcase_33	AC	2,576 ms 6,676 KB
testcase_34	AC	2,698 ms 6,676 KB
testcase_35	AC	2,668 ms 6,676 KB
testcase_36	AC	2,580 ms 6,676 KB
testcase_37	AC	2,524 ms 6,676 KB
testcase_38	AC	2,598 ms 6,676 KB
testcase_39	AC	2,440 ms 6,676 KB
testcase_40	AC	2,631 ms 6,676 KB
testcase_41	AC	2,660 ms 6,676 KB
testcase_42	AC	2,524 ms 6,676 KB
testcase_43	AC	2,493 ms 6,676 KB
testcase_44	AC	2,570 ms 6,676 KB
testcase_45	AC	2,714 ms 6,676 KB
testcase_46	AC	2,598 ms 6,676 KB
testcase_47	AC	2,469 ms 6,676 KB
testcase_48	AC	2,431 ms 6,676 KB
testcase_49	AC	2,502 ms 6,676 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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

ソースコード

raw source code

#[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;
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード