#1076705 (Rust) No.3121 Prime Dance

• 問題: No.3121 Prime Dance
• ユーザー: rhoo
• 提出日時: 2025-04-19 11:42:26
• 言語: Rust (1.83.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 6,880 bytes
• コンパイル時間: 13,776 ms
• コンパイル使用メモリ: 384,692 KB
• 実行使用メモリ: 82,304 KB
• 最終ジャッジ日時: 2025-04-19 11:42:43
• 合計ジャッジ時間: 16,402 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 17 WA * 4

コンパイルメッセージ

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&1!=0){
                if let Some(j_add)=solve(j0,j1,bit&2!=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)*)=>{}}