結果

問題 No.2657 Falling Block Game
ユーザー akakimidori
提出日時 2024-03-01 22:16:42
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 5,977 bytes
コンパイル時間 12,555 ms
コンパイル使用メモリ 397,660 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-09-29 14:18:17
合計ジャッジ時間 17,304 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
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>;
  |      ^^^^^

ソースコード

diff #
プレゼンテーションモードにする

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[mid] == 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>
where
T: 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>
where
T: 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) ----------
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0