結果
| 問題 |
No.3121 Prime Dance
|
| ユーザー |
 rhoo
|
| 提出日時 | 2025-04-19 11:43:45 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 213 ms / 2,000 ms |
| コード長 | 6,880 bytes |
| コンパイル時間 | 11,986 ms |
| コンパイル使用メモリ | 381,972 KB |
| 実行使用メモリ | 82,304 KB |
| 最終ジャッジ日時 | 2025-04-19 11:44:00 |
| 合計ジャッジ時間 | 14,841 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:299:7
|
299 | #[cfg(feature = "local")]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
= note: `#[warn(unexpected_cfgs)]` on by default
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:301:11
|
301 | #[cfg(not(feature = "local"))]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
ソースコード
#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,collections::*,iter::*};
use proconio::{marker::*,*};
#[fastout]
fn main(){
input!{
h:usize,
w:usize,
si:Usize1,
sj:Usize1,
gi:Usize1,
gj:Usize1,
map:[Chars;h],
}
let s=P::new(si,sj);
let g=P::new(gi,gj);
let isok=|p:P|->bool{
p.in_range(h,w) && map[p]!='#'
};
let mut able=vec![vec![0;w];h];
for i in 0..h{
for j in 0..w{
let p=P::new(i,j);
if !isok(p){
continue;
}
for k in 0..4{
let np=p+DD[k];
if isok(np){
if k==0 || k==2{
// move j
able[i][j]|=1;
} else{
// move i
able[i][j]|=2;
}
}
}
}
}
// debug!(able);
const INF:usize=usize::MAX/64;
let max_i_move=h*w;
let mut dist=vec![vec![vec![[INF;4];max_i_move+1];w];h];
dist[s][0][able[s]]=0;
let mut que=VecDeque::new();
que.push_back((s,0,able[s]));
while let Some((p,k,bit))=que.pop_front(){
let cd=dist[p][k][bit];
for i in 0..4{
let np=p+DD[i];
if !isok(np){
continue;
}
let nk=k+(i%2==1) as usize;
if nk>max_i_move{
continue;
}
let nbit=bit|able[np];
if dist[np][nk][nbit]>cd+1{
dist[np][nk][nbit]=cd+1;
que.push_back((np,nk,nbit));
}
}
}
let is_prime=(0..2000).map(|i|is_prime(i)).collect::<Vec<_>>();
let mut ans=INF;
let i_diff=si.abs_diff(gi);
let j_diff=sj.abs_diff(gj);
for i in 0..=max_i_move{
for bit in 0..4{
if dist[g][i][bit]==INF{
continue;
}
let i_mov=i;
let j_mov=dist[g][i][bit]-i_mov;
let i0=(i_mov+i_diff)/2;
let i1=(i_mov-i_diff)/2;
// eprintln!("{} {}",i_mov,i_diff);
assert!(i0+i1==i_mov && i0-i1==i_diff);
let j0=(j_mov+j_diff)/2;
let j1=(j_mov-j_diff)/2;
// eprintln!("{} {}",j_mov,j_diff);
assert!(j0+j1==j_mov && j0-j1==j_diff);
// eprintln!("{} {} {} {} {:b}",i0,i1,j0,j1,bit);
let solve=|i0:usize,i1:usize,able:bool|->Option<usize>{
if !able{
if is_prime[i0] && is_prime[i1]{
return Some(0);
}
return None;
}
if i0.max(i1)>3 && i0.abs_diff(i1)%2==1{
return None;
}
for add in 0..{
let ni0=i0+add;
let ni1=i1+add;
if is_prime.len()<=ni0 || is_prime.len()<=ni1{ // ここてきとーかも
// eprintln!("{} {}",i0,i1);
panic!();
// return None;
}
if is_prime[ni0] && is_prime[ni1]{
return Some(add);
}
}
panic!();
};
if let Some(i_add)=solve(i0,i1,bit&2!=0){
if let Some(j_add)=solve(j0,j1,bit&1!=0){
// eprintln!("{i0},{i1} +{i_add} {j0},{j1} +{j_add}");
ans=ans.min(i_mov+j_mov+i_add*2+j_add*2);
}
}
}
}
if ans==INF{
println!("-1");
} else{
println!("{ans}");
}
// println!("{ans}");
}
const DC:[char;4]=['L','U','R','D'];
const DD:[P;4]=[P{i:0,j:!0},P{i:!0,j:0},P{i:0,j:1},P{i:1,j:0}];
const DX:[P;8]=[P{i:0,j:!0},P{i:!0,j:!0},P{i:!0,j:0},P{i:!0,j:1},P{i:0,j:1},P{i:1,j:1},P{i:1,j:0},P{i:1,j:!0}];
const NULL:P=P{i:!0,j:!0};
#[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash)]
struct P{
i:usize,
j:usize,
}
impl P{
fn new(i:usize,j:usize)->P{
P{i,j}
}
fn in_range(self,h:usize,w:usize)->bool{
self.i<h && self.j<w
}
fn det(self,p:P)->i64{
(self.i*p.j-self.j*p.i) as i64
}
fn dot(self,p:P)->i64{
(self.i*p.i+self.j*p.j) as i64
}
fn manh(self,p:P)->usize{
fn abs_diff(a:usize,b:usize)->usize{
(a as i64-b as i64).abs() as usize
}
abs_diff(self.i,p.i)+abs_diff(self.j,p.j)
}
}
impl std::ops::Add for P{
type Output=P;
fn add(self,rhs:P)->P{
P{
i:self.i+rhs.i,
j:self.j+rhs.j,
}
}
}
impl std::ops::Sub for P{
type Output=P;
fn sub(self,rhs:P)->P{
P{
i:self.i-rhs.i,
j:self.j-rhs.j,
}
}
}
impl std::ops::Mul<usize> for P{
type Output=P;
fn mul(self,rhs:usize)->P{
P{
i:self.i*rhs,
j:self.j*rhs,
}
}
}
impl std::ops::Div<usize> for P{
type Output=P;
fn div(self,rhs:usize)->P{
P{
i:self.i/rhs,
j:self.j/rhs,
}
}
}
impl std::ops::Neg for P{
type Output=P;
fn neg(self)->P{
P{
i:self.i.wrapping_neg(),
j:self.j.wrapping_neg(),
}
}
}
impl std::ops::AddAssign for P{
fn add_assign(&mut self,rhs:P){
*self=*self+rhs;
}
}
impl std::ops::SubAssign for P{
fn sub_assign(&mut self,rhs:P){
*self=*self-rhs;
}
}
impl std::ops::MulAssign<usize> for P{
fn mul_assign(&mut self,rhs:usize){
*self=*self*rhs;
}
}
impl std::ops::DivAssign<usize> for P{
fn div_assign(&mut self,rhs:usize){
*self=*self/rhs;
}
}
impl<T:std::ops::Index<usize>> std::ops::Index<P> for [T]{
type Output=T::Output;
fn index(&self,idx:P)->&T::Output{
&self[idx.i][idx.j]
}
}
impl<T:std::ops::IndexMut<usize>> std::ops::IndexMut<P> for [T]{
fn index_mut(&mut self,idx:P)->&mut T::Output{
&mut self[idx.i][idx.j]
}
}
impl<T:std::ops::Index<usize>> std::ops::Index<P> for Vec<T>{
type Output=T::Output;
fn index(&self,idx:P)->&T::Output{
&self[idx.i][idx.j]
}
}
impl<T:std::ops::IndexMut<usize>> std::ops::IndexMut<P> for Vec<T>{
fn index_mut(&mut self,idx:P)->&mut T::Output{
&mut self[idx.i][idx.j]
}
}
fn is_prime(n:usize)->bool{
if n<=1{
return false;
}
for i in 2..{
if n<i*i{
break;
}
if n%i==0{
return false;
}
}
true
}
#[cfg(feature = "local")]
include!("../../.rs");
#[cfg(not(feature = "local"))]
#[macro_export]macro_rules! debug{($($t:tt)*)=>{}}