結果

問題 No.5006 Hidden Maze
ユーザー rhoorhoo
提出日時 2022-07-01 21:37:47
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,896 ms / 2,000 ms
コード長 5,536 bytes
コンパイル時間 2,964 ms
実行使用メモリ 22,856 KB
スコア 88,735
平均クエリ数 113.65
最終ジャッジ日時 2022-07-01 21:38:04
合計ジャッジ時間 14,605 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
21,952 KB
testcase_01 AC 1,896 ms
22,004 KB
testcase_02 AC 23 ms
21,992 KB
testcase_03 AC 24 ms
22,576 KB
testcase_04 AC 26 ms
21,940 KB
testcase_05 AC 22 ms
22,216 KB
testcase_06 AC 33 ms
21,768 KB
testcase_07 AC 24 ms
21,940 KB
testcase_08 AC 37 ms
22,552 KB
testcase_09 AC 39 ms
21,880 KB
testcase_10 AC 23 ms
21,892 KB
testcase_11 AC 28 ms
21,904 KB
testcase_12 AC 25 ms
22,264 KB
testcase_13 AC 25 ms
21,940 KB
testcase_14 AC 31 ms
22,576 KB
testcase_15 AC 30 ms
22,620 KB
testcase_16 AC 24 ms
22,620 KB
testcase_17 AC 21 ms
22,432 KB
testcase_18 AC 45 ms
22,216 KB
testcase_19 AC 26 ms
22,608 KB
testcase_20 AC 25 ms
22,796 KB
testcase_21 AC 31 ms
21,952 KB
testcase_22 AC 32 ms
21,892 KB
testcase_23 AC 29 ms
22,856 KB
testcase_24 AC 76 ms
22,004 KB
testcase_25 AC 25 ms
22,612 KB
testcase_26 AC 991 ms
21,952 KB
testcase_27 AC 34 ms
22,588 KB
testcase_28 AC 27 ms
22,468 KB
testcase_29 AC 24 ms
21,904 KB
testcase_30 AC 26 ms
22,456 KB
testcase_31 AC 23 ms
22,564 KB
testcase_32 AC 52 ms
22,552 KB
testcase_33 AC 27 ms
22,588 KB
testcase_34 AC 24 ms
21,880 KB
testcase_35 AC 24 ms
21,892 KB
testcase_36 AC 40 ms
22,204 KB
testcase_37 AC 53 ms
22,204 KB
testcase_38 AC 35 ms
21,952 KB
testcase_39 AC 40 ms
21,756 KB
testcase_40 AC 24 ms
21,660 KB
testcase_41 AC 28 ms
21,928 KB
testcase_42 AC 31 ms
22,564 KB
testcase_43 AC 34 ms
21,940 KB
testcase_44 AC 21 ms
22,276 KB
testcase_45 AC 48 ms
21,576 KB
testcase_46 AC 281 ms
22,704 KB
testcase_47 AC 29 ms
22,608 KB
testcase_48 AC 26 ms
21,904 KB
testcase_49 AC 65 ms
21,892 KB
testcase_50 AC 26 ms
21,928 KB
testcase_51 AC 24 ms
22,624 KB
testcase_52 AC 36 ms
21,928 KB
testcase_53 AC 32 ms
21,892 KB
testcase_54 AC 23 ms
21,780 KB
testcase_55 AC 29 ms
21,892 KB
testcase_56 AC 23 ms
21,768 KB
testcase_57 AC 76 ms
22,276 KB
testcase_58 AC 25 ms
21,780 KB
testcase_59 AC 27 ms
21,940 KB
testcase_60 AC 25 ms
21,892 KB
testcase_61 AC 22 ms
21,904 KB
testcase_62 AC 44 ms
21,992 KB
testcase_63 AC 29 ms
22,228 KB
testcase_64 AC 44 ms
22,276 KB
testcase_65 AC 22 ms
21,880 KB
testcase_66 AC 27 ms
22,456 KB
testcase_67 AC 46 ms
21,892 KB
testcase_68 AC 46 ms
22,612 KB
testcase_69 AC 33 ms
21,928 KB
testcase_70 AC 23 ms
21,904 KB
testcase_71 AC 24 ms
21,768 KB
testcase_72 AC 27 ms
21,904 KB
testcase_73 AC 32 ms
21,916 KB
testcase_74 AC 35 ms
22,276 KB
testcase_75 AC 47 ms
21,928 KB
testcase_76 AC 25 ms
21,892 KB
testcase_77 AC 40 ms
22,016 KB
testcase_78 AC 20 ms
22,564 KB
testcase_79 AC 60 ms
21,940 KB
testcase_80 AC 25 ms
22,588 KB
testcase_81 AC 29 ms
22,432 KB
testcase_82 AC 27 ms
22,576 KB
testcase_83 AC 21 ms
21,892 KB
testcase_84 AC 23 ms
21,768 KB
testcase_85 AC 29 ms
21,916 KB
testcase_86 AC 24 ms
22,216 KB
testcase_87 AC 43 ms
21,892 KB
testcase_88 AC 84 ms
22,264 KB
testcase_89 AC 81 ms
21,796 KB
testcase_90 AC 29 ms
21,892 KB
testcase_91 AC 35 ms
21,928 KB
testcase_92 AC 27 ms
22,240 KB
testcase_93 AC 29 ms
21,880 KB
testcase_94 AC 30 ms
21,980 KB
testcase_95 AC 37 ms
22,576 KB
testcase_96 AC 23 ms
22,632 KB
testcase_97 AC 41 ms
21,892 KB
testcase_98 AC 88 ms
22,004 KB
testcase_99 AC 29 ms
21,904 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,
    cnt:[[[i32;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,cnt:[[[0;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(&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 ret=loop{
            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;
            }
        };

        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.map[y][x][r]=0.;
                self.map[y+DY[r]][x+DX[r]][r^1]=0.;
            }

            let (y,x,r)=cmds[result as usize];
            if self.map[y][x][r]!=0.{
                self.cnt[y][x][r]+=1;
                self.map[y][x][r]=S*(1.-self.p).powi(self.cnt[y][x][r]) / (S*(1.-self.p).powi(self.cnt[y][x][r]) + (1.-S)*self.p.powi(self.cnt[y][x][r]));
                
                let (ny,nx,nr)=(y+DY[r],x+DX[r],r^1);
                self.cnt[ny][nx][nr]+=1;
                self.map[ny][nx][nr]=self.map[y][x][r];
            }
            
            self.log.push(cmds);
            
            false
        }
    }
}

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

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