結果

問題 No.5006 Hidden Maze
ユーザー rhoorhoo
提出日時 2022-07-02 00:34:12
言語 Rust
(1.77.0)
結果
AC  
実行時間 400 ms / 2,000 ms
コード長 6,623 bytes
コンパイル時間 7,507 ms
実行使用メモリ 22,856 KB
スコア 89,092
平均クエリ数 110.07
最終ジャッジ日時 2022-07-02 00:34:34
合計ジャッジ時間 15,581 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
22,004 KB
testcase_01 AC 400 ms
21,928 KB
testcase_02 AC 23 ms
21,880 KB
testcase_03 AC 22 ms
21,648 KB
testcase_04 AC 22 ms
22,228 KB
testcase_05 AC 37 ms
22,564 KB
testcase_06 AC 21 ms
22,264 KB
testcase_07 AC 24 ms
21,952 KB
testcase_08 AC 43 ms
21,880 KB
testcase_09 AC 23 ms
22,228 KB
testcase_10 AC 20 ms
22,228 KB
testcase_11 AC 18 ms
21,756 KB
testcase_12 AC 24 ms
22,432 KB
testcase_13 AC 21 ms
21,792 KB
testcase_14 AC 46 ms
22,216 KB
testcase_15 AC 22 ms
22,264 KB
testcase_16 AC 19 ms
21,904 KB
testcase_17 AC 19 ms
22,204 KB
testcase_18 AC 45 ms
22,552 KB
testcase_19 AC 19 ms
21,992 KB
testcase_20 AC 21 ms
22,704 KB
testcase_21 AC 20 ms
22,444 KB
testcase_22 AC 19 ms
21,928 KB
testcase_23 AC 25 ms
22,588 KB
testcase_24 AC 30 ms
22,288 KB
testcase_25 AC 23 ms
21,880 KB
testcase_26 AC 195 ms
22,844 KB
testcase_27 AC 23 ms
21,768 KB
testcase_28 AC 24 ms
21,928 KB
testcase_29 AC 91 ms
22,576 KB
testcase_30 AC 23 ms
22,276 KB
testcase_31 AC 19 ms
21,892 KB
testcase_32 AC 25 ms
21,928 KB
testcase_33 AC 22 ms
22,576 KB
testcase_34 AC 23 ms
21,768 KB
testcase_35 AC 31 ms
21,992 KB
testcase_36 AC 22 ms
22,004 KB
testcase_37 AC 45 ms
21,928 KB
testcase_38 AC 68 ms
22,252 KB
testcase_39 AC 26 ms
21,952 KB
testcase_40 AC 24 ms
21,892 KB
testcase_41 AC 28 ms
21,928 KB
testcase_42 AC 24 ms
21,892 KB
testcase_43 AC 29 ms
22,004 KB
testcase_44 AC 20 ms
21,928 KB
testcase_45 AC 31 ms
22,608 KB
testcase_46 AC 49 ms
22,216 KB
testcase_47 AC 29 ms
21,880 KB
testcase_48 AC 34 ms
21,904 KB
testcase_49 AC 152 ms
22,692 KB
testcase_50 AC 22 ms
22,252 KB
testcase_51 AC 24 ms
21,928 KB
testcase_52 AC 32 ms
22,264 KB
testcase_53 AC 28 ms
22,632 KB
testcase_54 AC 24 ms
21,892 KB
testcase_55 AC 21 ms
22,264 KB
testcase_56 AC 24 ms
21,892 KB
testcase_57 AC 31 ms
21,892 KB
testcase_58 AC 28 ms
22,004 KB
testcase_59 AC 25 ms
22,588 KB
testcase_60 AC 22 ms
22,692 KB
testcase_61 AC 19 ms
21,916 KB
testcase_62 AC 30 ms
21,868 KB
testcase_63 AC 21 ms
21,952 KB
testcase_64 AC 48 ms
21,892 KB
testcase_65 AC 47 ms
21,904 KB
testcase_66 AC 25 ms
21,756 KB
testcase_67 AC 28 ms
22,588 KB
testcase_68 AC 33 ms
22,620 KB
testcase_69 AC 24 ms
21,892 KB
testcase_70 AC 23 ms
21,928 KB
testcase_71 AC 23 ms
21,952 KB
testcase_72 AC 19 ms
21,952 KB
testcase_73 AC 35 ms
21,904 KB
testcase_74 AC 20 ms
21,880 KB
testcase_75 AC 22 ms
21,904 KB
testcase_76 AC 21 ms
21,928 KB
testcase_77 AC 40 ms
21,760 KB
testcase_78 AC 39 ms
22,856 KB
testcase_79 AC 52 ms
21,992 KB
testcase_80 AC 22 ms
22,228 KB
testcase_81 AC 29 ms
22,228 KB
testcase_82 AC 19 ms
22,612 KB
testcase_83 AC 21 ms
21,940 KB
testcase_84 AC 41 ms
21,904 KB
testcase_85 AC 25 ms
21,768 KB
testcase_86 AC 22 ms
22,856 KB
testcase_87 AC 20 ms
21,768 KB
testcase_88 AC 41 ms
22,564 KB
testcase_89 AC 115 ms
22,600 KB
testcase_90 AC 26 ms
21,928 KB
testcase_91 AC 21 ms
22,588 KB
testcase_92 AC 32 ms
22,264 KB
testcase_93 AC 25 ms
21,880 KB
testcase_94 AC 24 ms
21,940 KB
testcase_95 AC 23 ms
22,264 KB
testcase_96 AC 19 ms
21,940 KB
testcase_97 AC 43 ms
22,264 KB
testcase_98 AC 28 ms
22,612 KB
testcase_99 AC 20 ms
22,716 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused)]
mod rnd {
    static mut S:usize=88172645463325252;
    #[inline]
    pub fn next()->usize{
        unsafe{
            S=S^S<<7;
            S=S^S>>9;
            S
        }
    }

    #[inline]
    pub fn nextf()->f64{
        (next()&4294967295) as f64/4294967296.
    }
}


#[allow(unused)]
struct Scanner<'a>{
    stack:std::str::SplitAsciiWhitespace<'a>
}
#[allow(unused)]
impl<'a> Scanner<'a>{
    #[inline]
    fn new()->Self{
        Self{stack:"".split_ascii_whitespace()}
    }

    #[inline]
    fn read<T:std::str::FromStr>(&mut self)->T{
        loop{
            if let Some(v)=self.stack.next(){
                return v.parse::<T>().unwrap_or_else(|_|panic!("parse error"));
            }

            let mut tmp=String::new();
            std::io::stdin().read_line(&mut tmp).unwrap();
            assert!(!tmp.is_empty());
            self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
        }
    }
}


#[derive(PartialEq, PartialOrd)]
struct Hoge<T>(T);
impl<T:PartialEq> Eq for Hoge<T>{}

impl<T:PartialOrd> Ord for Hoge<T>{
    fn cmp(&self, other:&Self)->std::cmp::Ordering{
        self.0.partial_cmp(&other.0).unwrap()
    }
}


const N:usize=20;
const S:f64=0.19;


const DY:[usize;4]=[1,!0,0,0];
const DX:[usize;4]=[0,0,1,!0];
const DC:[char;4]=['D','U','R','L'];


struct Solver{
    p:f64,
    aru:[[[f64;4];N];N],
    nai:[[[f64;4];N];N],
    map:[[[f64;4];N];N],
    log:Vec<Vec<(usize,usize,usize)>> // y,x,r
}
impl Solver{
    #[inline]
    fn new(scan:&mut Scanner)->Solver{
        let h=scan.read();
        let w=scan.read();
        assert_eq!((h,w),(N,N));

        let p:usize=scan.read();
        let p=p as f64*0.01;

        Solver{
            p,
            aru:[[[S;4];N];N],
            nai:[[[1.-S;4];N];N],
            map:[[[S;4];N];N],
            log:vec![]
        }
    }

    #[inline]
    fn isok(&self,seen:&[[[usize;4];N];N],at:usize)->bool{
        'outer: for l in &self.log{
            for &(y,x,r) in l{
                if seen[y][x][r]!=at && self.map[y][x][r]!=0.{
                    continue 'outer;
                }
            }
            return false;
        }
        true
    }

    #[inline]
    fn next_cmds(&mut self)->Vec<(usize,usize,usize)>{
        let mut cur=vec![];
        
        let mut edge=[[[0.;4];N];N];
        let mut seen=[[0;N];N];
        let mut prev=[[!0;N];N];

        let mut at=0;
        let mut que=std::collections::BinaryHeap::new();

        let mut tmp=[[[0;4];N];N];

        let mut iter=1;
        let ret=loop{
            if iter&255==0 && rnd::next()&3==0{
                for i in 0..N{
                    for j in 0..N{
                        for k in 0..4{
                            self.aru[i][j][k]=S;
                            self.nai[i][j][k]=1.-S;
                            self.map[i][j][k]=S;
                        }
                    }
                }
            }
            for i in 0..N{
                for j in 0..N{
                    for k in 0..4{
                        edge[i][j][k]=self.map[i][j][k]*rnd::nextf();
                    }
                }
            }

            at+=1;
            que.clear();
            que.push((Hoge(1.),0,!0,(0,0)));

            while let Some((Hoge(f),_,r,(y,x)))=que.pop(){
                if seen[y][x]!=at{
                    seen[y][x]=at;
                    prev[y][x]=r;

                    if (y,x)==(N-1,N-1){
                        break;
                    }
                    else{
                        for (i,(&dy,&dx)) in DY.iter().zip(DX.iter()).enumerate(){
                            let ny=y+dy;
                            let nx=x+dx;
                            if ny<N && nx<N && seen[ny][nx]!=at{
                                que.push((Hoge((1.-edge[y][x][i])*f),rnd::next(),i,(ny,nx)));
                            }
                        }
                    }
                }
            }

            cur.clear();
            let mut pos=(N-1,N-1);
            while{
                let r=prev[pos.0][pos.1];

                if r==!0{
                    false
                }
                else{
                    tmp[pos.0][pos.1][r^1]=at;
                    pos.0+=DY[r^1];
                    pos.1+=DX[r^1];
                    cur.push((pos.0,pos.1,r));
                    tmp[pos.0][pos.1][r]=at;
                    
                    true
                }
            }{}

            if self.isok(&tmp,at){
                cur.reverse();
                break cur;
            }
            else{
                iter+=1;
            }
        };

        assert!(!ret.is_empty());

        ret
    }

    #[inline]
    fn run_cmds(&mut self,scan:&mut Scanner,cmds:Vec<(usize,usize,usize)>)->bool{
        for (_,_,r) in &cmds{
            print!("{}",DC[*r]);
        }
        println!();

        let result:i64=scan.read();
        if result==-1{
            true
        }
        else{
            for i in 0..result{
                let (y,x,r)=cmds[i as usize];
                self.aru[y][x][r]=0.;
                self.aru[y+DY[r]][x+DX[r]][r^1]=0.;
            }
            let (y,x,r)=cmds[result as usize];
            let (ny,nx,nr)=(y+DY[r],x+DX[r],r^1);
            self.aru[y][x][r]*=1.-self.p;
            self.aru[ny][nx][nr]=self.aru[y][x][r];
            self.nai[y][x][r]*=self.p;
            self.nai[ny][nx][nr]=self.nai[y][x][r];

            let mut sum=1.;
            for &(y,x,r) in &cmds{
                let aru=self.aru[y][x][r];
                let nai=self.nai[y][x][r];
                self.map[y][x][r]=aru/(aru+nai);
                sum*=1.-self.map[y][x][r];
                self.map[y+DY[r]][x+DX[r]][r^1]=self.map[y][x][r];
            }

            for &(y,x,r) in &cmds{
                self.nai[y][x][r]*=1.-sum/(1.-self.map[y][x][r]);
            }
            for &(y,x,r) in &cmds{
                let aru=self.aru[y][x][r];
                let nai=self.nai[y][x][r];
                self.map[y][x][r]=aru/(aru+nai);
                sum*=1.-self.map[y][x][r];
                self.map[y+DY[r]][x+DX[r]][r^1]=self.map[y][x][r];
            }

            self.log.push(cmds);
            
            false
        }
    }
}

fn main(){
    let mut scan=Scanner::new();
    let mut solver=Solver::new(&mut scan);
    
    let mut score=/*square*/1001;
    loop{
        score-=1;
        if score==0{break;}
        let next_cmds=solver.next_cmds();
        if solver.run_cmds(&mut scan,next_cmds){
            break;
        }
    }

    eprintln!("{:?}",score);
}
0