結果
問題 | No.2657 Falling Block Game |
ユーザー |
![]() |
提出日時 | 2024-03-01 22:12:46 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,976 bytes |
コンパイル時間 | 11,688 ms |
コンパイル使用メモリ | 392,724 KB |
実行使用メモリ | 8,076 KB |
最終ジャッジ日時 | 2024-09-29 14:12:36 |
合計ジャッジ時間 | 16,522 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 30 |
コンパイルメッセージ
warning: type alias `Map` is never used --> src/main.rs:4:6 | 4 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:5:6 | 5 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:6:6 | 6 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
use std::io::Write;use std::collections::*;type Map<K, V> = BTreeMap<K, V>;type Set<T> = BTreeSet<T>;type Deque<T> = VecDeque<T>;fn run() {input! {h: usize,w: usize,s: [bytes; h],}let inf = std::usize::MAX / 10;let mut dp = vec![0; w];for mut s in s.into_iter().rev() {let mut next = vec![inf; w];for _ in 0..2 {let rmq = RMQ::new(dp.clone());let mut cnt = vec![0; w + 1];for (i, c) in s.iter().enumerate().rev() {cnt[i] += cnt[i + 1];if *c == b'#' {cnt[i] += 1;}}for i in 0..w {if s[i] != b'#' {next[i] = next[i].min(dp[i]);}let mut ok = w;let mut ng = i;while ok - ng > 1 {let mid = (ok + ng) / 2;if cnt[i] - cnt[ok] == 0 && rmq.find(i, mid) <= mid - i - 1 {ok = mid;} else {ng = mid;}}next[i] = next[i].min((ok - i - 1).max(rmq.find(i, ok)));}dp.reverse();s.reverse();next.reverse();}dp = next;for (dp, s) in dp.iter_mut().zip(s.iter()) {if *s == b'#' {*dp = inf;}}}let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());for dp in dp {writeln!(out, "{}", dp).ok();}}fn main() {run();}// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8#[macro_export]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}#[macro_export]macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[macro_export]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------pub struct RMQ<T> {data: Vec<T>,table: SparseTable<T>,bit: Vec<usize>,}impl<T> RMQ<T>whereT: Ord + Copy,{pub fn new(data: Vec<T>) -> Self {assert!(!data.is_empty());let mut bit = vec![0; data.len()];let w = 8 * std::mem::size_of_val(&bit[0]);let mut stack: Vec<usize> = vec![];let mut table_ini = Vec::with_capacity((data.len() + w - 1) / w);for (bit, data) in bit.chunks_mut(w).zip(data.chunks(w)) {stack.clear();let mut b = 0;for (i, (bit, d)) in bit.iter_mut().zip(data.iter()).enumerate() {while stack.last().map_or(false, |x| data[*x] > *d) {b ^= 1 << stack.pop().unwrap();}b |= 1 << i;*bit = b;stack.push(i);}table_ini.push(data[stack[0]]);}let table = SparseTable::new(table_ini);RMQ { data, table, bit }}pub fn find(&self, l: usize, r: usize) -> T {assert!(l < r && r <= self.data.len());let w = 8 * std::mem::size_of_val(&self.bit[0]);let r = r - 1;let p = l / w;let q = r / w;if p == q {let pos = l + (self.bit[r] >> (l % w)).trailing_zeros() as usize;self.data[pos]} else {let pos = l + (self.bit[l / w * w + w - 1] >> (l % w)).trailing_zeros() as usize;let mut res = self.data[pos];let pos = r / w * w + (self.bit[r] >> 0).trailing_zeros() as usize;res = std::cmp::min(res, self.data[pos]);if l / w + 1 < r / w {res = std::cmp::min(res, self.table.find(l / w + 1, r / w));}res}}}// ---------- begin sparse table (min) ----------pub struct SparseTable<T> {table: Vec<Vec<T>>,size: usize,}impl<T> SparseTable<T>whereT: Ord + Copy,{pub fn new(mut a: Vec<T>) -> Self {assert!(a.len() > 0);let size = a.len();let mut table = vec![];let mut w = 1;while w + 1 <= a.len() {let next = a.iter().zip(a[w..].iter()).map(|p| std::cmp::min(*p.0, *p.1)).collect::<Vec<_>>();table.push(a);a = next;w <<= 1;}table.push(a);SparseTable {table: table,size: size,}}pub fn find(&self, l: usize, r: usize) -> T {assert!(l < r && r <= self.size);let k = (r - l + 1).next_power_of_two().trailing_zeros() as usize - 1;let table = &self.table[k];std::cmp::min(table[l], table[r - (1 << k)])}}// ---------- end sparse table (min) ----------