結果
| 問題 | No.2657 Falling Block Game |
| ユーザー |
 akakimidori
|
| 提出日時 | 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>
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) ----------