結果
| 問題 |
No.1434 Make Maze
|
| コンテスト | |
| ユーザー |
 くれちー
|
| 提出日時 | 2021-03-19 23:57:36 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 30 ms / 2,000 ms |
| コード長 | 10,928 bytes |
| コンパイル時間 | 28,578 ms |
| コンパイル使用メモリ | 382,804 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-24 21:47:19 |
| 合計ジャッジ時間 | 20,592 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
// The main code is at the very bottom.
#[allow(unused_imports)]
use {
lib::byte::ByteChar,
std::cell::{Cell, RefCell},
std::cmp::{
self,
Ordering::{self, *},
Reverse,
},
std::collections::*,
std::convert::identity,
std::fmt::{self, Debug, Display, Formatter},
std::io::prelude::*,
std::iter::{self, FromIterator},
std::marker::PhantomData,
std::mem,
std::num::Wrapping,
std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive},
std::process,
std::rc::Rc,
std::thread,
std::time::{Duration, Instant},
std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize},
};
#[allow(unused_imports)]
#[macro_use]
pub mod lib {
pub mod byte {
pub use self::byte_char::*;
mod byte_char {
use std::error::Error;
use std::fmt::{self, Debug, Display, Formatter};
use std::str::FromStr;
#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct ByteChar(pub u8);
impl Debug for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "b'{}'", self.0 as char)
}
}
impl Display for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{}", self.0 as char)
}
}
impl FromStr for ByteChar {
type Err = ParseByteCharError;
fn from_str(s: &str) -> Result<ByteChar, ParseByteCharError> {
match s.as_bytes().len() {
1 => Ok(ByteChar(s.as_bytes()[0])),
0 => Err(ParseByteCharErrorKind::EmptyStr.into()),
_ => Err(ParseByteCharErrorKind::TooManyBytes.into()),
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct ParseByteCharError {
kind: ParseByteCharErrorKind,
}
impl Display for ParseByteCharError {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.write_str(match self.kind {
ParseByteCharErrorKind::EmptyStr => "empty string",
ParseByteCharErrorKind::TooManyBytes => "too many bytes",
})
}
}
impl Error for ParseByteCharError {}
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum ParseByteCharErrorKind {
EmptyStr,
TooManyBytes,
}
impl From<ParseByteCharErrorKind> for ParseByteCharError {
fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError {
ParseByteCharError { kind }
}
}
}
}
pub mod io {
pub use self::scanner::*;
mod scanner {
use std::io::{self, BufRead};
use std::iter;
use std::str::FromStr;
#[derive(Debug)]
pub struct Scanner<R> {
reader: R,
buf: String,
pos: usize,
}
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Scanner {
reader,
buf: String::new(),
pos: 0,
}
}
pub fn next(&mut self) -> io::Result<&str> {
let start = loop {
match self.rest().find(|c| c != ' ') {
Some(i) => break i,
None => self.fill_buf()?,
}
};
self.pos += start;
let len = self.rest().find(' ').unwrap_or(self.rest().len());
let s = &self.buf[self.pos..][..len]; // self.rest()[..len]
self.pos += len;
Ok(s)
}
pub fn parse_next<T>(&mut self) -> io::Result<Result<T, T::Err>>
where
T: FromStr,
{
Ok(self.next()?.parse())
}
pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>
where
T: FromStr,
{
iter::repeat_with(|| self.parse_next()).take(n).collect()
}
pub fn map_next_bytes<T, F>(&mut self, mut f: F) -> io::Result<Vec<T>>
where
F: FnMut(u8) -> T,
{
Ok(self.next()?.bytes().map(&mut f).collect())
}
pub fn map_next_bytes_n<T, F>(&mut self, n: usize, mut f: F) -> io::Result<Vec<Vec<T>>>
where
F: FnMut(u8) -> T,
{
iter::repeat_with(|| self.map_next_bytes(&mut f))
.take(n)
.collect()
}
fn rest(&self) -> &str {
&self.buf[self.pos..]
}
fn fill_buf(&mut self) -> io::Result<()> {
self.buf.clear();
self.pos = 0;
let read = self.reader.read_line(&mut self.buf)?;
if read == 0 {
return Err(io::ErrorKind::UnexpectedEof.into());
}
if *self.buf.as_bytes().last().unwrap() == b'\n' {
self.buf.pop();
}
Ok(())
}
}
}
}
}
#[allow(unused_macros)]
macro_rules! eprint {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::eprint!($($arg)*)
}
};
}
#[allow(unused_macros)]
macro_rules! eprintln {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::eprintln!($($arg)*)
}
};
}
#[allow(unused_macros)]
macro_rules! dbg {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::dbg!($($arg)*)
} else {
($($arg)*)
}
};
}
const CUSTOM_STACK_SIZE_MIB: Option<usize> = Some(1024);
const INTERACTIVE: bool = false;
fn main() -> std::io::Result<()> {
match CUSTOM_STACK_SIZE_MIB {
Some(stack_size_mib) => std::thread::Builder::new()
.name("run_solver".to_owned())
.stack_size(stack_size_mib * 1024 * 1024)
.spawn(run_solver)?
.join()
.unwrap(),
None => run_solver(),
}
}
fn run_solver() -> std::io::Result<()> {
let stdin = std::io::stdin();
let reader = stdin.lock();
let stdout = std::io::stdout();
let writer = stdout.lock();
macro_rules! with_wrapper {
($($wrapper:expr)?) => {{
let mut writer = $($wrapper)?(writer);
solve(reader, &mut writer)?;
writer.flush()
}};
}
if cfg!(debug_assertions) || INTERACTIVE {
with_wrapper!()
} else {
with_wrapper!(std::io::BufWriter::new)
}
}
fn solve<R, W>(reader: R, mut writer: W) -> std::io::Result<()>
where
R: BufRead,
W: Write,
{
let mut _scanner = lib::io::Scanner::new(reader);
#[allow(unused_macros)]
macro_rules! scan {
($T:ty) => {
_scanner.parse_next::<$T>()?.unwrap()
};
($($T:ty),+) => {
($(scan!($T)),+)
};
($T:ty; $n:expr) => {
_scanner.parse_next_n::<$T>($n)?.unwrap()
};
($($T:ty),+; $n:expr) => {
iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) })
.take($n)
.collect::<std::io::Result<Vec<_>>>()?
};
}
#[allow(unused_macros)]
macro_rules! scan_bytes_map {
($f:expr) => {
_scanner.map_next_bytes($f)?
};
($f:expr; $n:expr) => {
_scanner.map_next_bytes_n($n, $f)?
};
}
#[allow(unused_macros)]
macro_rules! print {
($($arg:tt)*) => {
write!(writer, $($arg)*)?
};
}
#[allow(unused_macros)]
macro_rules! println {
($($arg:tt)*) => {
writeln!(writer, $($arg)*)?
};
}
#[allow(unused_macros)]
macro_rules! answer {
($($arg:tt)*) => {{
println!($($arg)*);
return Ok(());
}};
}
{
let (h, w, x) = scan!(usize, usize, usize);
if x % 2 != 0 || x < (w - 1) + (h - 1) {
answer!("-1");
}
if (h, w) == (3, 3) {
if x != 4 {
answer!("-1");
}
answer!("...\n##.\n...");
}
let rev = w == 3;
let (w, h) = if rev { (h, w) } else { (w, h) };
let h2 = h / 2 + 1;
let w2 = w / 2 + 1;
let x2 = x / 2 + 1;
let mut p0 = (0..w)
.step_by(4)
.take_while(|&c| c + 4 < w)
.map(|c| (0, c))
.collect::<Vec<_>>();
p0.reverse();
let s = p0[0].1 + 2;
let mut p1 = if w2 % 2 != 0 {
vec![]
} else {
(0..h)
.rev()
.step_by(4)
.take_while(|&r| r >= 4)
.map(|r| (s, r - 2))
.collect()
};
let mut ans = vec![vec![false; w]; h];
for r in 0..h {
for c in 0..w {
if r == 0 || c == w - 1 || r % 2 == 0 && c % 2 == 0 {
ans[r][c] = true;
}
}
}
if w2 % 2 == 0 && h2 % 2 == 0 {
ans[2][w - 4] = true;
}
let mut cur = h2 + w2 - 1;
loop {
if let Some((r, c)) = p0.pop() {
ans[r + 1][c] = true;
ans[r + 1][c + 2] = true;
if cur < x2 {
ans[r + 2][c + 1] = true;
ans[r][c + 1] = false;
}
if r + 2 != h - 1 {
p0.push((r + 2, c));
}
} else if let Some((c, r)) = p1.pop() {
ans[r][c + 1] = true;
ans[r + 2][c + 1] = true;
if cur < x2 {
ans[r + 1][c + 2] = true;
ans[r + 1][c] = false;
}
if c + 4 != w - 1 {
p1.push((c + 2, r));
}
} else {
break;
}
if cur < x2 {
cur += 2;
}
}
if cur != x2 {
answer!("-1");
}
if !rev {
for r in 0..h {
for c in 0..w {
print!("{}", ByteChar(if ans[r][c] { b'.' } else { b'#' }));
}
println!();
}
} else {
for c in 0..w {
for r in 0..h {
print!("{}", ByteChar(if ans[r][c] { b'.' } else { b'#' }));
}
println!();
}
}
// check
// {
// for r in 0..h {
// for c in 0..w {
// if r % 2 != 0 && c % 2 != 0 {
// assert!(!ans[r][c]);
// }
// if r % 2 == 0 && c % 2 == 0 {
// assert!(ans[r][c]);
// }
// }
// }
// let mut g = vec![vec![vec![]; w]; h];
// for r in 0..h {
// for c in 0..w {
// if r + 1 < h && ans[r][c] && ans[r + 1][c] {
// g[r][c].push((r + 1, c));
// g[r + 1][c].push((r, c));
// }
// if c + 1 < w && ans[r][c] && ans[r][c + 1] {
// g[r][c].push((r, c + 1));
// g[r][c + 1].push((r, c));
// }
// }
// }
// let mut stack = vec![];
// let mut visited = vec![vec![false; w]; h];
// stack.push((0, 0, None, 0));
// visited[0][0] = true;
// while let Some((r, c, prev, d)) = stack.pop() {
// for &(r2, c2) in &g[r][c] {
// if Some((r2, c2)) == prev {
// continue;
// }
// if visited[r2][c2] {
// panic!("{} {}", r2, c2);
// }
// visited[r2][c2] = true;
// if (r2, c2) == (h - 1, w - 1) {
// assert_eq!(d + 1, x);
// }
// stack.push((r2, c2, Some((r, c)), d + 1));
// }
// }
// for r in 0..h {
// for c in 0..w {
// assert_eq!(visited[r][c], ans[r][c], "{} {}", r, c);
// }
// }
// }
}
#[allow(unreachable_code)]
Ok(())
}