結果

問題 No.1328 alligachi-problem
ユーザー くれちー
提出日時 2020-12-25 02:03:20
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 10,292 bytes
コンパイル時間 15,716 ms
コンパイル使用メモリ 383,612 KB
実行使用メモリ 27,164 KB
最終ジャッジ日時 2024-09-21 17:26:12
合計ジャッジ時間 22,598 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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

// 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(());
}};
}
{
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum Color {
R,
B,
}
fn parse_color(c: ByteChar) -> Color {
match c.0 {
b'R' => Color::R,
b'B' => Color::B,
_ => unreachable!(),
}
}
let n = scan!(usize);
let cxy = scan!(ByteChar, ByteChar, usize; n);
let (mut cnt_r, mut cnt_b) = {
let cnt = |color| {
cxy
.iter()
.filter(|&&(c, _, _)| parse_color(c) == color)
.count()
};
(cnt(Color::R), cnt(Color::B))
};
let mut balls = HashMap::<(Color, Color, usize), Vec<usize>>::new();
for (i, &(c, x, y)) in cxy.iter().enumerate() {
balls
.entry((parse_color(c), parse_color(x), y))
.or_default()
.push(i);
}
let mut ans = Vec::with_capacity(n);
while cnt_r > 0 || cnt_b > 0 {
let rr = cnt_r
.checked_sub(1)
.and_then(|t| balls.get(&(Color::R, Color::R, t)).map(Vec::len))
.unwrap_or(0);
let rb = balls
.get(&(Color::R, Color::B, cnt_b))
.map(Vec::len)
.unwrap_or(0);
let br = balls
.get(&(Color::B, Color::R, cnt_r))
.map(Vec::len)
.unwrap_or(0);
let bb = cnt_b
.checked_sub(1)
.and_then(|t| balls.get(&(Color::B, Color::B, t)).map(Vec::len))
.unwrap_or(0);
if br > 0 && rb > 0 {
answer!("No");
}
if rr > 1 || bb > 1 {
answer!("No");
}
let prev_ans_len = ans.len();
macro_rules! ans_push {
($k:expr) => {
ans.push(balls.get_mut(&$k).unwrap().pop().unwrap());
};
}
if br > 0 {
if bb == 1 {
ans_push!((Color::B, Color::B, cnt_b - 1));
cnt_b -= 1;
continue;
}
ans_push!((Color::B, Color::R, cnt_r));
cnt_b -= 1;
continue;
} else {
if rr == 1 {
ans_push!((Color::R, Color::R, cnt_r - 1));
cnt_r -= 1;
continue;
}
if rb > 0 {
ans_push!((Color::R, Color::B, cnt_b));
cnt_r -= 1;
continue;
}
if bb == 1 {
ans_push!((Color::B, Color::B, cnt_b - 1));
cnt_b -= 1;
continue;
}
}
if ans.len() == prev_ans_len {
answer!("No");
}
}
println!("Yes");
for i in (0..n).rev() {
print!("{}", ans[i] + 1);
if i == 0 {
println!();
} else {
print!(" ");
}
}
// {
// let mut cnt_r = 0usize;
// let mut cnt_b = 0usize;
// for i in (0..n).rev() {
// let (c, x, y) = cxy[ans[i]];
// match parse_color(x) {
// Color::R => assert_eq!(y, cnt_r),
// Color::B => assert_eq!(y, cnt_b),
// }
// match parse_color(c) {
// Color::R => cnt_r += 1,
// Color::B => cnt_b += 1,
// }
// }
// }
}
#[allow(unreachable_code)]
Ok(())
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0