結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 rhoo
|
| 提出日時 | 2022-08-02 00:21:51 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 997 ms / 1,000 ms |
| コード長 | 22,609 bytes |
| コンパイル時間 | 4,045 ms |
| 実行使用メモリ | 3,164 KB |
| スコア | 9,057,560 |
| 最終ジャッジ日時 | 2022-08-02 00:22:27 |
| 合計ジャッジ時間 | 36,794 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
warning: variable `score` is assigned to, but never used
--> Main.rs:821:13
|
821 | let mut score=0;
| ^^^^^
|
= note: `#[warn(unused_variables)]` on by default
= note: consider using `_score` instead
warning: unused variable: `p`
--> Main.rs:462:13
|
462 | let p=up as f64/iter as f64;
| ^ help: if this is intentional, prefix it with an underscore: `_p`
warning: unused variable: `p`
--> Main.rs:711:13
|
711 | let p=up as f64/iter as f64;
| ^ help: if this is intentional, prefix it with an underscore: `_p`
warning: unused variable: `p`
--> Main.rs:807:13
|
807 | let p=up as f64/I as f64;
| ^ help: if this is intentional, prefix it with an underscore: `_p`
warning: 4 warnings emitted
ソースコード
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, Chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, Usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
#[allow(unused)]
#[inline]
fn get_time()->f64{
static mut START:f64=-1.;
let t=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
unsafe{
if START<0.{START=t;}
t-START
}
}
#[cfg(local)]
#[allow(unused)]
macro_rules! debug{
()=>{
eprintln!();
};
($x:literal)=>{
eprintln!("{:?}",$x);
};
($x:expr)=>{
eprintln!("{}: {:?}",stringify!($x),$x);
};
($x:literal,$($l:expr),*)=>{
eprint!("{:?}, ",$x);
debug!($($l),*);
};
($x:expr,$($l:expr),*)=>{
eprint!("{}: {:?}, ",stringify!($x),$x);
debug!($($l),*);
}
}
#[cfg(not(local))]
#[allow(unused)]
macro_rules! debug{
($($_:expr),*)=>{}
}
#[allow(unused)]
mod rnd {
static mut S:usize=88172645463325252;
#[inline]
pub fn next()->usize{
unsafe{
S^=S<<7;
S^=S>>9;
S
}
}
#[inline]
pub fn nextf()->f64{
unsafe{
std::mem::transmute::<_,f64>(0x3ff0000000000000|next()&0xfffffffffffff)-1.
}
}
// [a,b)
#[inline]
pub fn range(a:usize,b:usize)->usize{
next()%(b-a)+a
}
#[inline]
pub fn rangei(a:i64,b:i64)->i64{
(next()>>1) as i64%(b-a)+a
}
#[inline]
pub fn shuffle<T>(list:&mut [T]){
for i in (0..list.len()).rev(){
list.swap(i,next()%(i+1));
}
}
}
const N:usize=100;
const M:usize=8;
const A:i64=5;
#[inline]
fn get_dist(p1:(usize,usize),p2:(usize,usize))->i64{
let y=p1.0-p2.0;
let x=p1.1-p2.1;
(y*y+x*x) as i64
}
macro_rules! get{
($self:ident,$a:ident)=>{
($self.route[$a-1],$self.route[$a])
};
}
macro_rules! dist{
($self:ident;$($a:ident,$b:ident);*)=>{
0$(+$self.dist[$a][$b])*
}
}
pub struct In{
pos:[(usize,usize);N]
}
impl In{
#[inline]
fn input()->In{
input!{
n:usize,
m:usize,
tp:[(usize,usize);N]
}
assert_eq!((n,m),(N,M));
let mut it=tp.into_iter();
In{pos:[();N].map(|_|it.next().unwrap())}
}
}
// ステーションの大体の位置を求める
mod solver1{
use super::*;
struct Out{
m:[(usize,usize);M],
dist:[[i64;N];N],
cnt:[usize;N+M],
route:Vec<usize>,
log:Vec<(bool,usize)> // type,idx
}
impl Out{
#[inline]
fn new(input:&In)->Out{
let mut route=(0..N).collect::<Vec<_>>();
route.push(0);
rnd::shuffle(&mut route[1..N]);
let mut cnt=[0;N+M];
cnt[0]=2;
cnt[1..N].fill(1);
cnt[N..N+M].fill(usize::MAX>>1);
let m=[();M].map(|_|(rnd::next()%1001,rnd::next()%1001));
let mut dist=[[i64::MAX>>2;N];N];
for i in 0..N{
for j in 0..N{
dist[i][j]=A*A*get_dist(input.pos[i],input.pos[j]);
}
}
for k in 0..N{
for i in 0..N{
for j in 0..N{
dist[i][j]=dist[i][j].min(dist[i][k]+dist[k][j]);
}
}
}
Out{m,dist,cnt,route,log:vec![]}
}
#[inline]
fn reset(&mut self){
self.route=(0..N).collect::<Vec<_>>();
self.route.push(0);
rnd::shuffle(&mut self.route[1..N]);
self.cnt[0]=2;
self.cnt[1..N].fill(1);
self.cnt[N..N+M].fill(usize::MAX>>1);
self.m=[();M].map(|_|(rnd::next()%1001,rnd::next()%1001));
}
#[inline]
fn score(&self,input:&In)->i64{
self.route.windows(2).map(|w|self.dist(input,w[0],w[1])).sum::<i64>()
}
#[inline]
// #[track_caller]
fn dist(&self,input:&In,a:usize,b:usize)->i64{
if a<N && b<N{
self.dist[a][b]
}
else if a>=N && b>=N{
get_dist(self.m[a-N],self.m[b-N])
}
else if a>=N{
A*get_dist(self.m[a-N],input.pos[b])
}
else{
A*get_dist(self.m[b-N],input.pos[a])
}
}
#[inline]
fn sub(&self,input:&In,a:usize,p:(usize,usize))->i64{
if a<N{
get_dist(input.pos[a],p)*A
}
else{
get_dist(self.m[a-N],p)
}
}
#[inline]
// idxは+Nされたあと
fn change(&mut self,input:&In,add:i64,id:usize,new:(usize,usize),score:&mut i64)->bool{
self.log.clear();
let mut prev=self.route[0];
let mut f=false;
let mut at=1;
let mut diff=0;
for &v in &self.route[1..]{
if f{
diff+=self.dist(input,prev,v)-self.dist(input,prev,id)-self.dist(input,id,v);
}
if v!=id{
let d=self.sub(input,prev,new)+self.sub(input,v,new)-self.dist(input,prev,v);
if 0>d{
diff+=d;
self.log.push((true,at));
at+=1;
}
prev=v;
at+=1;
f=false;
}
else{
self.log.push((false,at));
f=true;
}
}
if add>=diff{
*score+=diff;
self.m[id-N]=new;
for &(t,idx) in &self.log{
if t{
self.route.insert(idx,id);
}
else{
self.route.remove(idx);
}
}
true
}
else{
false
}
}
#[inline]
fn try_opt2(&self,input:&In,a:usize,b:usize)->i64{
let (a0,a1)=get!(self,a);
let (b0,b1)=get!(self,b);
self.dist(input,a0,b0)+self.dist(input,a1,b1)-self.dist(input,a0,a1)-self.dist(input,b0,b1)
}
#[inline]
fn opt2(&mut self,mut a:usize,mut b:usize){
if a>b{
std::mem::swap(&mut a,&mut b);
}
self.route[a..b].reverse();
}
#[inline]
fn try_insert(&self,input:&In,idx:usize,v:usize)->i64{
let (v0,v1)=get!(self,idx);
self.dist(input,v0,v)+self.dist(input,v,v1)-self.dist(input,v0,v1)
}
#[inline]
fn insert(&mut self,idx:usize,v:usize){
self.route.insert(idx,v);
self.cnt[v]+=1;
}
#[inline]
fn try_remove(&self,input:&In,idx:usize)->i64{
let (v0,v1)=get!(self,idx);
let v2=self.route[idx+1];
self.dist(input,v0,v2)-self.dist(input,v0,v1)-self.dist(input,v1,v2)
}
#[inline]
fn remove(&mut self,idx:usize){
let v=self.route.remove(idx);
self.cnt[v]-=1;
}
}
pub fn sa(input:&In)->([(usize,usize);M],Vec<usize>){
const TL:f64=0.88;
let mut best=i64::MAX;
let mut best_state=([(!0,!0);M],vec![]);
let mut iter=0;
let mut up=0;
let mut th=[0;256];
let mut cur=Out::new(input);
const I:usize=5;
debug!("solver1");
for i in 0..I{
cur.reset();
let mut score=cur.score(input);
let start=get_time();
let tl=TL*(i+1) as f64/I as f64;
loop{
if iter&1023==0{
let p=(get_time()-start)/(tl-start);
if p>=1.{break;}
const T:f64=35000.;
let heat=T*(1.-p);
th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
}
let r=rnd::nextf();
const A:f64=0.5; // 2-opt
const B:f64=0.2; // insert
const C:f64=0.2; // remove
// const D:f64=0.1; // change
if r<=A{
let a=rnd::range(1,cur.route.len()-1);
let mut b;
while{
b=rnd::range(1,cur.route.len()-1);
a-b+1<=2
}{}
let diff=cur.try_opt2(input,a,b);
if th[iter&255]>=diff{
score+=diff;
cur.opt2(a,b);
up+=1;
}
}
else if r<=A+B{
let idx=rnd::range(1,cur.route.len());
let mut v;
while{
v=rnd::next()%(N+M);
v==cur.route[idx-1] || v==cur.route[idx]
}{}
let diff=cur.try_insert(input,idx,v);
if th[iter&255]>=diff{
score+=diff;
cur.insert(idx,v);
up+=1;
}
}
else if r<=A+B+C && cur.route.len()!=N+1{
let mut idx;
while{
idx=rnd::range(1,cur.route.len()-1);
let v=cur.route[idx];
cur.cnt[v]==1
}{}
let diff=cur.try_remove(input,idx);
if th[iter&255]>=diff{
score+=diff;
cur.remove(idx);
up+=1;
}
}
else{
const R:i64=100;
let id=rnd::next()&7;
let p=cur.m[id];
let mut np;
while{
np=(p.0+rnd::rangei(-R,R+1) as usize,p.1+rnd::rangei(-R,R+1) as usize);
np.0>1000 || np.1>1000 || np==p
}{}
if cur.change(input,th[iter&255],id+N,np,&mut score){
up+=1;
}
}
iter+=1;
if best>score{
best=score;
best_state=(cur.m,cur.route.clone());
}
}
debug!(i,score);
}
let p=up as f64/iter as f64;
debug!(iter,p);
debug!(best);
debug!(best_state.1.len());
debug!();
best_state
}
}
// 得られたステーションから経路を求める
mod solver2{
use super::*;
struct Out{
next:[[usize;N+M];N+M],
dist:[[i64;N];N],
route:[usize;N+1]
}
impl Out{
#[inline]
fn new(input:&In,m:&[(usize,usize);M],route:[usize;N+1])->Out{
let mut dist_sub=[[i64::MAX>>2;N+M];N+M];
let mut next=[[!0;N+M];N+M];
for i in 0..N+M{
let a=if i<N{input.pos[i]}else{m[i-N]};
for j in 0..N+M{
let b=if j<N{input.pos[j]}else{m[j-N]};
dist_sub[i][j]=get_dist(a,b)*if i<N && j<N{A*A}
else if i>=N && j>=N{1}
else{A};
next[i][j]=j;
}
}
for k in 0..N+M{
for i in 0..N+M{
for j in 0..N+M{
if dist_sub[i][j]>dist_sub[i][k]+dist_sub[k][j]{
next[i][j]=next[i][k];
dist_sub[i][j]=dist_sub[i][k]+dist_sub[k][j];
}
}
}
}
let mut dist=[[!0;N];N];
for i in 0..N{
for j in 0..N{
dist[i][j]=dist_sub[i][j];
}
}
Out{next,dist,route}
}
#[inline]
fn score(&self)->i64{
self.route.windows(2).map(|w|self.dist[w[0]][w[1]]).sum::<i64>()
}
#[inline]
fn try_opt2(&self,a:usize,b:usize)->i64{
let (a0,a1)=get!(self,a);
let (b0,b1)=get!(self,b);
dist!(self;a0,b0;a1,b1)-dist!(self;a0,a1;b0,b1)
}
#[inline]
fn opt2(&mut self,mut a:usize,mut b:usize){
if a>b{
std::mem::swap(&mut a,&mut b);
}
self.route[a..b].reverse();
}
#[inline]
fn try_db(&self,a:usize,b:usize,c:usize,d:usize)->i64{
// assert!(0<a && a+1<b && b+1<c && c+1<d && d<self.route.len());
let (a0,a1)=get!(self,a);
let (b0,b1)=get!(self,b);
let (c0,c1)=get!(self,c);
let (d0,d1)=get!(self,d);
dist!(self;a0,c1;d0,b1;c0,a1;b0,d1)-dist!(self;a0,a1;b0,b1;c0,c1;d0,d1)
}
#[inline]
fn db(&mut self,a:usize,b:usize,c:usize,d:usize){
self.route[b..d].rotate_right(d-c);
self.route[a..d].rotate_right(d-b);
}
#[inline]
fn try_opt3(&mut self,a:usize,b:usize,c:usize,t:usize)->i64{
// assert!(0<a && a+1<b && b+1<c && c<self.route.len());
let (a0,a1)=get!(self,a);
let (b0,b1)=get!(self,b);
let (c0,c1)=get!(self,c);
let old=dist!(self;a0,a1;b0,b1;c0,c1);
if t==0{
dist!(self;a0,b0;a1,c0;b1,c1)-old
}
else if t==1{
dist!(self;a0,c0;b1,a1;b0,c1)-old
}
else if t==2{
dist!(self;a0,b1;c0,b0;a1,c1)-old
}
else{
dist!(self;a0,b1;c0,a1;b0,c1)-old
}
}
#[inline]
fn opt3(&mut self,a:usize,b:usize,c:usize,t:usize){
if t&1==0{
self.route[a..b].reverse();
}
if t<=1{
self.route[b..c].reverse();
}
if t!=0{
self.route[a..c].rotate_right(c-b);
}
}
#[inline]
fn build(&self)->Vec<usize>{
let mut ret=vec![0];
for w in self.route.windows(2){
let mut s=w[0];
let t=w[1];
while s!=t{
s=self.next[s][t];
ret.push(s);
}
}
ret
}
}
pub fn sa(input:&In,m:&[(usize,usize);M],route:Vec<usize>)->Vec<usize>{
let mut cur={
let mut seen=[true;N+M];
let mut it=route.into_iter().filter(|&x|{
let f=seen[x];
seen[x]=false;
x<N && f
}).chain(0..=0);
Out::new(input,m,[0;N+1].map(|_|it.next().unwrap()))
};
let mut score=cur.score();
debug!("solver2");
debug!(score);
let mut best=score;
let mut best_state=cur.route;
let mut iter=0;
let mut up=0;
let mut th=[0;256];
let start=get_time();
loop{
if iter&1023==0{
const TL:f64=0.98;
let p=(get_time()-start)/(TL-start);
if p>=1.{
break;
}
const T0:f64=10000.;
const T1:f64=0.;
let heat=T0+(T1-T0)*p;
th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
}
iter+=1;
const A:f64=0.8; // 2-opt
const B:f64=0.1; // 3-opt
// const C:f64=0.1; // double-bridge
let r=rnd::nextf();
if r<=A{
let a=rnd::range(1,cur.route.len());
let mut b;
while{
b=rnd::range(1,cur.route.len());
a-b+1<=2
}{}
let diff=cur.try_opt2(a,b);
if th[iter&255]>=diff{
cur.opt2(a,b);
score+=diff;
up+=1;
}
}
else{
let mut x=[rnd::range(1,cur.route.len()),!0,!0,!0];
while{
x[1]=rnd::range(1,cur.route.len());
x[0]-x[1]+1<=2
}{}
while{
x[2]=rnd::range(1,cur.route.len());
x[0]-x[2]+1<=2 || x[1]-x[2]+1<=2
}{}
if r<=A+B{
x[..3].sort_unstable();
let t=rnd::next()&3;
let diff=cur.try_opt3(x[0],x[1],x[2],t);
if th[iter&255]>=diff{
cur.opt3(x[0],x[1],x[2],t);
score+=diff;
up+=1;
}
}
else{
while{
x[3]=rnd::range(1,cur.route.len());
x[0]-x[3]+1<=2 || x[1]-x[3]+1<=2 || x[2]-x[3]+1<=2
}{}
x.sort_unstable();
let diff=cur.try_db(x[0],x[1],x[2],x[3]);
if th[iter&255]>=diff{
cur.db(x[0],x[1],x[2],x[3]);
score+=diff;
up+=1;
}
}
}
best=best.min(score);
}
let p=up as f64/iter as f64;
debug!(iter,p);
debug!(score,best);
debug!();
std::mem::swap(&mut best_state,&mut cur.route);
cur.build()
}
}
// 得られた経路からステーションの位置を微調整
mod solver3{
use super::*;
const DY:[usize;8]=[1,0,!0,0,1,1,!0,!0];
const DX:[usize;8]=[0,1,0,!0,1,!0,1,!0];
// 重複しているやつのinitをうまくやること！
struct Out{
m:[(usize,usize);M],
path:[Vec<usize>;M]
}
impl Out{
#[inline]
fn new(m:[(usize,usize);M],route:&[usize])->Out{
let mut path=[();M].map(|_|vec![]);
for w in route.windows(2){
if N <=w[0]{
path[w[0]-N].push(w[1]);
}
if N <=w[1]{
path[w[1]-N].push(w[0]);
}
}
Out{m,path}
}
#[inline]
fn score(&self,input:&In)->i64{
let mut ret=0;
for i in 0..M{
for &j in self.path[i].iter(){
if j<=i+N{
ret+=self.dist(input,j,self.m[i]);
}
}
}
ret
}
#[inline]
fn dist(&self,input:&In,a:usize,p:(usize,usize))->i64{
if a<N{
A*get_dist(input.pos[a],p)
}
else{
get_dist(self.m[a-N],p)
}
}
#[inline]
fn try_change(&self,input:&In,idx:usize,np:(usize,usize))->i64{
let old=self.path[idx].iter().map(|&x|self.dist(input,x,self.m[idx])).sum::<i64>();
let new=self.path[idx].iter().map(|&x|self.dist(input,x,np)).sum::<i64>();
new-old
}
}
pub fn hc(input:&In,m:[(usize,usize);M],route:&[usize])->[(usize,usize);M]{
let mut cur=Out::new(m,route);
let mut score=cur.score(input);
const I:usize=200000;
let mut up=0;
for _ in 0..I{
let mut tr=rnd::next();
let idx=tr>>32&7;
let p=cur.m[idx];
let mut np;
while{
let dr=tr&7;
np=(p.0+DY[dr],p.1+DX[dr]);
np.0>1000 || np.1>1000
}{tr=rnd::next();}
let diff=cur.try_change(input,idx,np);
if 0>=diff{
score+=diff;
cur.m[idx]=np;
up+=1;
}
}
assert_eq!(score,cur.score(input));
let p=up as f64/I as f64;
debug!(p);
cur.m
}
}
fn main(){
let input=In::input();
let (m,route)=solver1::sa(&input);
let route=solver2::sa(&input,&m,route);
let m=solver3::hc(&input,m,&route);
let mut score=0;
for w in route.windows(2){
let s=if w[0]<N{input.pos[w[0]]}else{m[w[0]-N]};
let t=if w[1]<N{input.pos[w[1]]}else{m[w[1]-N]};
score+=get_dist(s,t)*if w[0]<N && w[1]<N{A*A}
else if w[0]>=N && w[1]>=N{1}
else{A};
}
debug!(score);
// println!("{}",(1000000000./(1000.+(score as f64).sqrt())).round());
for (a,b) in m{
println!("{a} {b}");
}
println!("{}",route.len());
for v in route{
if v<N{
println!("1 {}",v+1);
}
else{
println!("2 {}",v-N+1);
}
}
debug!(get_time());
}