Hyper Tomato (BOJ 17114)

solution.rs

use core::mem::MaybeUninit;

use alloc::collections::VecDeque;
use basm::io;

const D: usize = 11;
pub fn main() {
    let mut reader = io::Reader::<{ 1 << 15 }>::new();
    let mut writer = io::Writer::<32>::new();
    let mut tomato: [u8; (1_000_000 + 7) / 8] = unsafe { MaybeUninit::uninit().assume_init() };
    let mut size: [usize; D] = unsafe { MaybeUninit::uninit().assume_init() };
    for i in 0..D {
        size[i] = reader.next_usize();
    }
    let mut unit: [usize; D + 1] = unsafe { MaybeUninit::uninit().assume_init() };
    unit[0] = 1;
    for i in 0..D {
        unit[i + 1] = unit[i] * size[i];
    }
    for i in 0..=unit[D] / 8 {
        tomato[i] = 0;
    }
    let mut queue = VecDeque::<u32>::new();
    let mut full = 0;
    for i in 0..unit[D] {
        let mut buf = [0, 0];
        reader.next_word(&mut buf);
        match buf[0] {
            b'0' => {
                full += 1;
            }
            b'1' => {
                queue.push_back(i as u32);
                tomato[i / 8] |= 1 << (i % 8);
            }
            _ => {
                tomato[i / 8] |= 1 << (i % 8);
            }
        };
    }
    let mut day = 0usize;
    let mut remain = queue.len();
    while let Some(pos) = queue.pop_front() {
        let pos = pos as usize;
        for i in 0..D {
            if pos % unit[i + 1] >= unit[i] {
                let next = pos - unit[i];
                if tomato[next / 8] & (1 << (next % 8)) == 0 {
                    tomato[next / 8] |= 1 << (next % 8);
                    queue.push_back(next as u32);
                }
            }
            if pos % unit[i + 1] + unit[i] < unit[i + 1] {
                let next = pos + unit[i];
                if tomato[next / 8] & (1 << (next % 8)) == 0 {
                    tomato[next / 8] |= 1 << (next % 8);
                    queue.push_back(next as u32);
                }
            }
        }
        remain -= 1;
        if remain == 0 {
            day += 1;
            full -= queue.len();
            remain = queue.len();
        }
    }
    if full > 0 {
        writer.write(b"-1");
    } else {
        writer.write_usize(day.saturating_sub(1));
    }
}