結果
問題 | No.2731 Two Colors |
ユーザー | Yukino DX. |
提出日時 | 2024-04-20 09:54:50 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 134 ms / 3,000 ms |
コード長 | 4,217 bytes |
コンパイル時間 | 12,139 ms |
コンパイル使用メモリ | 398,052 KB |
実行使用メモリ | 26,380 KB |
最終ジャッジ日時 | 2024-10-12 05:19:58 |
合計ジャッジ時間 | 15,770 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 117 ms
26,380 KB |
testcase_01 | AC | 128 ms
26,376 KB |
testcase_02 | AC | 134 ms
26,376 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 6 ms
6,820 KB |
testcase_05 | AC | 5 ms
6,816 KB |
testcase_06 | AC | 15 ms
6,816 KB |
testcase_07 | AC | 15 ms
7,040 KB |
testcase_08 | AC | 3 ms
6,820 KB |
testcase_09 | AC | 56 ms
20,068 KB |
testcase_10 | AC | 2 ms
6,816 KB |
testcase_11 | AC | 70 ms
17,152 KB |
testcase_12 | AC | 56 ms
20,072 KB |
testcase_13 | AC | 63 ms
14,976 KB |
testcase_14 | AC | 29 ms
9,728 KB |
testcase_15 | AC | 3 ms
6,816 KB |
testcase_16 | AC | 26 ms
8,236 KB |
testcase_17 | AC | 35 ms
11,588 KB |
testcase_18 | AC | 7 ms
6,820 KB |
testcase_19 | AC | 29 ms
8,448 KB |
testcase_20 | AC | 35 ms
14,080 KB |
testcase_21 | AC | 8 ms
6,816 KB |
testcase_22 | AC | 65 ms
19,584 KB |
testcase_23 | AC | 17 ms
6,816 KB |
testcase_24 | AC | 8 ms
6,820 KB |
testcase_25 | AC | 1 ms
6,816 KB |
testcase_26 | AC | 48 ms
16,512 KB |
testcase_27 | AC | 60 ms
20,048 KB |
testcase_28 | AC | 43 ms
12,544 KB |
testcase_29 | AC | 14 ms
6,820 KB |
testcase_30 | AC | 25 ms
8,288 KB |
testcase_31 | AC | 17 ms
6,820 KB |
testcase_32 | AC | 79 ms
22,960 KB |
testcase_33 | AC | 1 ms
6,816 KB |
testcase_34 | AC | 1 ms
6,820 KB |
testcase_35 | AC | 1 ms
6,816 KB |
ソースコード
#![allow(unused_imports)] //use itertools::{iproduct, Itertools}; use proconio::input; use proconio::marker::*; use std::cmp::Reverse; use std::collections::*; fn main() { input! { h:usize, w:usize, a:[[usize;w];h], } let mut pq = [BinaryHeap::new(), BinaryHeap::new()]; let mut seen = [vec![vec![false; w]; h], vec![vec![false; w]; h]]; seen[1][0][0] = true; seen[0][h - 1][w - 1] = true; for Pos { x, y } in Pos::new(0, 0).neigh4(h, w) { pq[1].push(Reverse((a[x][y], x, y))); seen[1][x][y] = true; } for Pos { x, y } in Pos::new(h - 1, w - 1).neigh4(h, w) { pq[0].push(Reverse((a[x][y], x, y))); seen[0][x][y] = true; } let mut ans = 0; let mut mod2 = 1; let mut colors = vec![vec![2; w]; h]; colors[0][0] = 1; colors[h - 1][w - 1] = 0; while let Some(Reverse((_, x, y))) = pq[mod2].pop() { if colors[x][y] != 2 { continue; } ans += 1; colors[x][y] = mod2; if Pos::new(x, y) .neigh4(h, w) .any(|Pos { x: nx, y: ny }| colors[nx][ny] == 1 - mod2) { break; } for Pos { x: nx, y: ny } in Pos::new(x, y).neigh4(h, w) { if seen[mod2][nx][ny] { continue; } pq[mod2].push(Reverse((a[nx][ny], nx, ny))); seen[mod2][nx][ny] = true; } mod2 = 1 - mod2; } println!("{}", ans); } use grid_mgr::*; mod grid_mgr { //[R,D,L,U] pub const DIR4: [(usize, usize); 4] = [(0, 1), (1, 0), (0, !0), (!0, 0)]; pub const DIR8: [(usize, usize); 8] = [ (1, 0), (1, !0), (0, !0), (!0, !0), (!0, 0), (!0, 1), (0, 1), (1, 1), ]; pub struct Pos { pub x: usize, pub y: usize, } impl Pos { #[allow(dead_code)] pub fn new(x: usize, y: usize) -> Self { Self { x, y } } #[allow(dead_code)] pub fn neigh4<'a>(&'a self, h: usize, w: usize) -> impl Iterator<Item = Pos> + 'a { DIR4.iter().filter_map(move |&(dx, dy)| { let nx = self.x.wrapping_add(dx); let ny = self.y.wrapping_add(dy); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } }) } #[allow(dead_code)] pub fn neigh8<'a>(&'a self, h: usize, w: usize) -> impl Iterator<Item = Pos> + 'a { DIR8.iter().filter_map(move |&(dx, dy)| { let nx = self.x.wrapping_add(dx); let ny = self.y.wrapping_add(dy); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } }) } #[allow(dead_code)] pub fn line<'a>( &'a self, h: usize, w: usize, dir: (usize, usize), ) -> impl Iterator<Item = Pos> + 'a { (0..).map_while(move |i| { let nx = self.x.wrapping_add(dir.0.wrapping_mul(i)); let ny = self.y.wrapping_add(dir.1.wrapping_mul(i)); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } }) } #[allow(dead_code)] pub fn _moveto(&self, h: usize, w: usize, dir: (usize, usize)) -> Option<Pos> { let nx = self.x.wrapping_add(dir.0); let ny = self.y.wrapping_add(dir.1); if nx < h && ny < w { Some(Pos::new(nx, ny)) } else { None } } #[allow(dead_code)] pub fn moveto(&self, h: usize, w: usize, dir: char) -> Option<Pos> { match dir { 'R' => self._moveto(h, w, DIR4[0]), 'D' => self._moveto(h, w, DIR4[1]), 'L' => self._moveto(h, w, DIR4[2]), 'U' => self._moveto(h, w, DIR4[3]), _ => unreachable!(), } } } }