Submission #5905603
Source Code Expand
pub trait Readable {
type Output;
fn words_count() -> usize;
fn read_words(words: &[&str]) -> Result<Self::Output, String>;
}
#[macro_export]
macro_rules! readable {
( $ t : ty , $ words_count : expr , |$ words : ident | $ read_words : expr ) => {
impl Readable for $t {
type Output = $t;
fn words_count() -> usize {
$words_count
}
fn read_words($words: &[&str]) -> Result<$t, String> {
Ok($read_words)
}
}
};
}
readable!((), 1, |_ss| ());
readable!(String, 1, |ss| ss[0].to_string());
impl Readable for char {
type Output = char;
fn words_count() -> usize {
1
}
fn read_words(words: &[&str]) -> Result<char, String> {
let chars: Vec<char> = words[0].chars().collect();
if chars.len() == 1 {
Ok(chars[0])
} else {
Err(format!("cannot parse `{}` as a char", words[0]))
}
}
}
pub struct Chars();
impl Readable for Chars {
type Output = Vec<char>;
fn words_count() -> usize {
1
}
fn read_words(words: &[&str]) -> Result<Vec<char>, String> {
Ok(words[0].chars().collect())
}
}
macro_rules ! impl_readable_for_ints { ( $ ( $ t : ty ) * ) => { $ ( impl Readable for $ t { type Output = Self ; fn words_count ( ) -> usize { 1 } fn read_words ( words : & [ & str ] ) -> Result <$ t , String > { use std :: str :: FromStr ; <$ t >:: from_str ( words [ 0 ] ) . map_err ( | _ | { format ! ( "cannot parse `{}` as {}" , words [ 0 ] , stringify ! ( $ t ) ) } ) } } ) * } ; }
impl_readable_for_ints ! ( i8 u8 i16 u16 i32 u32 i64 u64 isize usize f32 f64 ) ;
macro_rules ! define_one_origin_int_types { ( $ new_t : ident $ int_t : ty ) => { # [ doc = " Converts 1-origin integer into 0-origin when read from stdin." ] # [ doc = "" ] # [ doc = " # Example" ] # [ doc = "" ] # [ doc = " ```no_run" ] # [ doc = " # #[macro_use] extern crate atcoder_snippets;" ] # [ doc = " # use atcoder_snippets::read::*;" ] # [ doc = " // Stdin: \"1\"" ] # [ doc = " read!(a = usize_);" ] # [ doc = " assert_eq!(a, 0);" ] # [ doc = " ```" ] # [ allow ( non_camel_case_types ) ] pub struct $ new_t ; impl Readable for $ new_t { type Output = $ int_t ; fn words_count ( ) -> usize { 1 } fn read_words ( words : & [ & str ] ) -> Result < Self :: Output , String > { <$ int_t >:: read_words ( words ) . map ( | n | n - 1 ) } } } ; ( $ new_t : ident $ int_t : ty ; $ ( $ inner_new_t : ident $ inner_int_t : ty ) ;* ) => { define_one_origin_int_types ! ( $ new_t $ int_t ) ; define_one_origin_int_types ! ( $ ( $ inner_new_t $ inner_int_t ) ;* ) ; } ; }
define_one_origin_int_types ! ( u8_ u8 ; u16_ u16 ; u32_ u32 ; u64_ u64 ; usize_ usize ) ;
macro_rules ! impl_readable_for_tuples { ( $ t : ident $ var : ident ) => ( ) ; ( $ t : ident $ var : ident ; $ ( $ inner_t : ident $ inner_var : ident ) ;* ) => { impl_readable_for_tuples ! ( $ ( $ inner_t $ inner_var ) ;* ) ; impl <$ t : Readable , $ ( $ inner_t : Readable ) ,*> Readable for ( $ t , $ ( $ inner_t ) ,* ) { type Output = ( <$ t >:: Output , $ ( <$ inner_t >:: Output ) ,* ) ; fn words_count ( ) -> usize { let mut n = <$ t >:: words_count ( ) ; $ ( n += <$ inner_t >:: words_count ( ) ; ) * n } # [ allow ( unused_assignments ) ] fn read_words ( words : & [ & str ] ) -> Result < Self :: Output , String > { let mut start = 0 ; let $ var = <$ t >:: read_words ( & words [ start .. start +<$ t >:: words_count ( ) ] ) ?; start += <$ t >:: words_count ( ) ; $ ( let $ inner_var = <$ inner_t >:: read_words ( & words [ start .. start +<$ inner_t >:: words_count ( ) ] ) ?; start += <$ inner_t >:: words_count ( ) ; ) * Ok ( ( $ var , $ ( $ inner_var ) ,* ) ) } } } ; }
impl_readable_for_tuples ! ( T8 x8 ; T7 x7 ; T6 x6 ; T5 x5 ; T4 x4 ; T3 x3 ; T2 x2 ; T1 x1 ) ;
pub trait ReadableFromLine {
type Output;
fn read_line(line: &str) -> Result<Self::Output, String>;
}
fn split_into_words(line: &str) -> Vec<&str> {
#[allow(deprecated)]
line.trim_right_matches('\n').split_whitespace().collect()
}
impl<T: Readable> ReadableFromLine for T {
type Output = T::Output;
fn read_line(line: &str) -> Result<T::Output, String> {
let words = split_into_words(line);
if words.len() != T::words_count() {
return Err(format!(
"line `{}` has {} words, expected {}",
line,
words.len(),
T::words_count()
));
}
T::read_words(&words)
}
}
macro_rules ! impl_readable_from_line_for_tuples_with_from_iterator { ( $ u : ident : $ ( + $ bound : path ) * => $ seq_in : ty , $ seq_out : ty ; $ t : ident $ var : ident ) => { impl <$ u : Readable > ReadableFromLine for $ seq_in where <$ u as Readable >:: Output : Sized $ ( + $ bound ) * { type Output = $ seq_out ; fn read_line ( line : & str ) -> Result <$ seq_out , String > { let n = $ u :: words_count ( ) ; let words = split_into_words ( line ) ; if words . len ( ) % n != 0 { return Err ( format ! ( "line `{}` has {} words, expected multiple of {}" , line , words . len ( ) , n ) ) ; } let mut result = Vec :: new ( ) ; for chunk in words . chunks ( n ) { match $ u :: read_words ( chunk ) { Ok ( v ) => result . push ( v ) , Err ( msg ) => { let flagment_msg = if n == 1 { format ! ( "word {}" , result . len ( ) ) } else { let l = result . len ( ) ; format ! ( "words {}-{}" , n * l + 1 , ( n + 1 ) * l ) } ; return Err ( format ! ( "{} of line `{}`: {}" , flagment_msg , line , msg ) ) ; } } } Ok ( result . into_iter ( ) . collect ( ) ) } } impl < T : Readable , $ u : Readable > ReadableFromLine for ( T , $ seq_in ) where <$ u as Readable >:: Output : Sized $ ( + $ bound ) * { type Output = ( T :: Output , $ seq_out ) ; fn read_line ( line : & str ) -> Result < Self :: Output , String > { let n = T :: words_count ( ) ; # [ allow ( deprecated ) ] let trimmed = line . trim_right_matches ( '\n' ) ; let words_and_rest : Vec <& str > = trimmed . splitn ( n + 1 , ' ' ) . collect ( ) ; if words_and_rest . len ( ) < n { return Err ( format ! ( "line `{}` has {} words, expected at least {}" , line , words_and_rest . len ( ) , n ) ) ; } let words = & words_and_rest [ .. n ] ; let empty_str = "" ; let rest = words_and_rest . get ( n ) . unwrap_or ( & empty_str ) ; Ok ( ( T :: read_words ( words ) ?, <$ seq_in >:: read_line ( rest ) ? ) ) } } } ; ( $ u : ident : $ ( + $ bound : path ) * => $ seq_in : ty , $ seq_out : ty ; $ t : ident $ var : ident , $ ( $ inner_t : ident $ inner_var : ident ) ,+ ) => { impl_readable_from_line_for_tuples_with_from_iterator ! ( $ u : $ ( + $ bound ) * => $ seq_in , $ seq_out ; $ ( $ inner_t $ inner_var ) ,+ ) ; impl <$ t : Readable , $ ( $ inner_t : Readable ) ,+ , $ u : Readable > ReadableFromLine for ( $ t , $ ( $ inner_t ) ,+ , $ seq_in ) where <$ u as Readable >:: Output : Sized $ ( + $ bound ) * { type Output = ( $ t :: Output , $ ( $ inner_t :: Output ) ,+ , $ seq_out ) ; fn read_line ( line : & str ) -> Result < Self :: Output , String > { let mut n = $ t :: words_count ( ) ; $ ( n += $ inner_t :: words_count ( ) ; ) + # [ allow ( deprecated ) ] let trimmed = line . trim_right_matches ( '\n' ) ; let words_and_rest : Vec <& str > = trimmed . splitn ( n + 1 , ' ' ) . collect ( ) ; if words_and_rest . len ( ) < n { return Err ( format ! ( "line `{}` has {} words, expected at least {}" , line , words_and_rest . len ( ) , n ) ) ; } let words = & words_and_rest [ .. n ] ; let empty_str = "" ; let rest = words_and_rest . get ( n ) . unwrap_or ( & empty_str ) ; let ( $ var , $ ( $ inner_var ) ,* ) = < ( $ t , $ ( $ inner_t ) ,+ ) >:: read_words ( words ) ?; Ok ( ( $ var , $ ( $ inner_var ) ,* , <$ seq_in >:: read_line ( rest ) ? ) ) } } } ; }
#[macro_export]
macro_rules ! readable_collection { ( $ u : ident => $ collection_in : ty , $ collection_out : ty ) => { impl_readable_from_line_for_tuples_with_from_iterator ! ( $ u : => $ collection_in , $ collection_out ; T8 x8 , T7 x7 , T6 x6 , T5 x5 , T4 t4 , T3 t3 , T2 t2 , T1 t1 ) ; } ; ( $ u : ident : $ ( $ bound : path ) ,* => $ collection_in : ty , $ collection_out : ty ) => { impl_readable_from_line_for_tuples_with_from_iterator ! ( $ u : $ ( + $ bound ) * => $ collection_in , $ collection_out ; T8 x8 , T7 x7 , T6 x6 , T5 x5 , T4 t4 , T3 t3 , T2 t2 , T1 t1 ) ; } }
readable_collection ! ( U => Vec < U >, Vec < U :: Output > ) ;
readable_collection ! ( U : Eq , std :: hash :: Hash => std :: collections :: HashSet < U >, std :: collections :: HashSet < U :: Output > ) ;
pub fn read<T: ReadableFromLine>() -> T::Output {
let mut line = String::new();
std::io::stdin().read_line(&mut line).unwrap();
T::read_line(&line).unwrap()
}
#[macro_export]
macro_rules ! read { ( ) => { let mut line = String :: new ( ) ; std :: io :: stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; } ; ( $ pat : pat = $ t : ty ) => { let $ pat = read ::<$ t > ( ) ; } ; ( $ ( $ pat : pat = $ t : ty ) ,+ ) => { read ! ( ( $ ( $ pat ) ,* ) = ( $ ( $ t ) ,* ) ) ; } ; }
#[macro_export]
macro_rules ! readls { ( $ ( $ pat : pat = $ t : ty ) ,+ ) => { $ ( read ! ( $ pat = $ t ) ; ) * } ; }
pub fn readx<T: ReadableFromLine>() -> Vec<T::Output> {
use std::io::{self, BufRead};
let stdin = io::stdin();
let result = stdin
.lock()
.lines()
.map(|line_result| {
let line = line_result.expect("read from stdin failed");
T::read_line(&line).unwrap()
})
.collect();
result
}
#[macro_export]
macro_rules ! readx_loop { ( |$ pat : pat = $ t : ty | $ body : expr ) => { use std :: io :: BufRead ; let stdin = std :: io :: stdin ( ) ; for line in stdin . lock ( ) . lines ( ) { let line = line . expect ( "read from stdin failed" ) ; let $ pat = <$ t >:: read_line ( & line ) . unwrap ( ) ; $ body } } ; ( |$ ( $ pat : pat = $ t : ty ) ,*| $ body : expr ) => { readx_loop ! ( | ( $ ( $ pat ) ,* ) = ( $ ( $ t ) ,* ) | $ body ) ; } ; }
pub fn readn<T: ReadableFromLine>(n: usize) -> Vec<T::Output> {
use std::io::{self, BufRead};
let stdin = io::stdin();
let result: Vec<T::Output> = stdin
.lock()
.lines()
.take(n)
.map(|line_result| {
let line = line_result.expect("read from stdin failed");
T::read_line(&line).unwrap()
})
.collect();
if result.len() < n {
panic!(
"expected reading {} lines, but only {} lines are read",
n,
result.len()
);
}
result
}
#[macro_export]
macro_rules ! readn_loop { ( $ n : expr , |$ pat : pat = $ t : ty | $ body : expr ) => { use std :: io :: BufRead ; let stdin = std :: io :: stdin ( ) ; { let mut lock = stdin . lock ( ) ; for _ in 0 ..$ n { let mut line = String :: new ( ) ; lock . read_line ( & mut line ) . expect ( "read from stdin failed" ) ; let $ pat = <$ t >:: read_line ( & line ) . unwrap ( ) ; $ body } } } ; ( $ n : expr , |$ ( $ pat : pat = $ t : ty ) ,*| $ body : expr ) => { readn_loop ! ( $ n , | ( $ ( $ pat ) ,* ) = ( $ ( $ t ) ,* ) | $ body ) ; } ; }
pub trait Words {
fn read<T: Readable>(&self) -> T::Output;
}
impl<'a> Words for [&'a str] {
fn read<T: Readable>(&self) -> T::Output {
T::read_words(self).unwrap()
}
}
impl<'a> Words for &'a str {
fn read<T: Readable>(&self) -> T::Output {
T::read_words(&[self]).unwrap()
}
}
#[derive(Clone)]
pub struct StepBy<I> {
iter: I,
step: usize,
first_take: bool,
}
impl<I: Iterator> Iterator for StepBy<I> {
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
if self.first_take {
self.first_take = false;
self.iter.next()
} else {
self.iter.nth(self.step)
}
}
}
#[derive(Clone)]
pub struct LScan<I: Iterator, S: Clone, F: FnMut(&S, I::Item) -> S> {
iter: I,
state: Option<S>,
f: F,
}
impl<I: Iterator, S: Clone, F> Iterator for LScan<I, S, F>
where
F: FnMut(&S, I::Item) -> S,
{
type Item = S;
fn next(&mut self) -> Option<S> {
if self.state.is_none() {
return None;
}
let state_inner = self.state.take().unwrap();
if let Some(item) = self.iter.next() {
self.state = Some((self.f)(&state_inner, item));
}
Some(state_inner)
}
}
pub struct Flatten<I: Iterator>
where
I::Item: IntoIterator,
{
outer_iter: I,
inner_iter: Option<<<I as Iterator>::Item as IntoIterator>::IntoIter>,
}
impl<I, J> Iterator for Flatten<I>
where
I: Iterator<Item = J>,
J: IntoIterator,
{
type Item = <<J as IntoIterator>::IntoIter as Iterator>::Item;
fn next(&mut self) -> Option<J::Item> {
loop {
if let Some(inner_iter) = self.inner_iter.as_mut() {
if let item @ Some(_) = inner_iter.next() {
return item;
}
}
match self.outer_iter.next() {
None => return None,
Some(inner) => self.inner_iter = Some(inner.into_iter()),
}
}
}
}
pub struct GroupBy<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> {
cur: Option<(I::Item, K)>,
iter: I,
key_fn: F,
}
impl<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> Iterator for GroupBy<K, I, F> {
type Item = (K, Vec<I::Item>);
fn next(&mut self) -> Option<(K, Vec<I::Item>)> {
let cur = self.cur.take();
cur.map(|(item, key)| {
let mut group = vec![item];
loop {
let next = self.iter.next();
match next {
Some(next_item) => {
let next_key = (self.key_fn)(&next_item);
if key == next_key {
group.push(next_item);
} else {
self.cur = Some((next_item, next_key));
break;
}
}
None => {
self.cur = None;
break;
}
}
}
(key, group)
})
}
}
pub trait IteratorExt: Iterator {
fn step_by_(self, step: usize) -> StepBy<Self>
where
Self: Sized,
{
assert_ne!(step, 0);
StepBy {
iter: self,
step: step - 1,
first_take: true,
}
}
fn for_each<F: FnMut(Self::Item)>(self, mut f: F)
where
Self: Sized,
{
for item in self {
f(item);
}
}
fn lscan<S: Clone, F>(self, state: S, f: F) -> LScan<Self, S, F>
where
Self: Sized,
F: FnMut(&S, Self::Item) -> S,
{
LScan {
iter: self,
state: Some(state),
f: f,
}
}
fn get_unique(mut self) -> Option<Self::Item>
where
Self: Sized,
Self::Item: Eq,
{
let first_opt = self.next();
first_opt.and_then(|first| {
if self.all(|item| item == first) {
Some(first)
} else {
None
}
})
}
fn flatten(mut self) -> Flatten<Self>
where
Self: Sized,
Self::Item: IntoIterator,
{
let inner_opt = self.next();
Flatten {
outer_iter: self,
inner_iter: inner_opt.map(|inner| inner.into_iter()),
}
}
fn group_by<K: Eq, F: FnMut(&Self::Item) -> K>(mut self, mut f: F) -> GroupBy<K, Self, F>
where
Self: Sized,
{
let next = self.next();
GroupBy {
cur: next.map(|item| {
let key = f(&item);
(item, key)
}),
iter: self,
key_fn: f,
}
}
fn join(mut self, sep: &str) -> String
where
Self: Sized,
Self::Item: std::fmt::Display,
{
let mut result = String::new();
if let Some(first) = self.next() {
result.push_str(&format!("{}", first));
}
for s in self {
result.push_str(&format!("{}{}", sep, s));
}
result
}
fn cat(self) -> String
where
Self: Sized,
Self::Item: std::fmt::Display,
{
self.join("")
}
}
impl<I: Iterator> IteratorExt for I {}
pub struct Unfold<T, F>
where
F: FnMut(&T) -> Option<T>,
{
state: Option<T>,
f: F,
}
impl<T, F> Iterator for Unfold<T, F>
where
F: FnMut(&T) -> Option<T>,
{
type Item = T;
fn next(&mut self) -> Option<T> {
if self.state.is_none() {
return None;
}
let state_inner = self.state.take().unwrap();
self.state = (self.f)(&state_inner);
Some(state_inner)
}
}
pub fn unfold<T, F>(init: T, f: F) -> Unfold<T, F>
where
F: FnMut(&T) -> Option<T>,
{
Unfold {
state: Some(init),
f: f,
}
}
pub struct Iterate<T, F>
where
F: FnMut(&T) -> T,
{
state: T,
f: F,
}
impl<T, F> Iterator for Iterate<T, F>
where
F: FnMut(&T) -> T,
{
type Item = T;
fn next(&mut self) -> Option<T> {
use std::mem::swap;
let mut state = (self.f)(&self.state);
swap(&mut state, &mut self.state);
Some(state)
}
}
pub fn iterate<T, F>(init: T, f: F) -> Iterate<T, F>
where
F: FnMut(&T) -> T,
{
Iterate { state: init, f: f }
}
fn main() {
read!();
read!(s = String);
let w_count = s.chars().filter(|&c| c == '.').count();
let ans = s.chars().lscan((0, w_count), |&(b, w), c| {
if c == '#' {
(b+1, w)
} else {
(b, w-1)
}
}).map(|(b, w)| b+w).min().unwrap();
println!("{}", ans);
}
Submission Info
Submission Time |
|
Task |
C - Stones |
User |
avtomat |
Language |
Rust (1.15.1) |
Score |
300 |
Code Size |
17758 Byte |
Status |
AC |
Exec Time |
4 ms |
Memory |
4352 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, s1.txt, s2.txt, s3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
4 ms |
4352 KB |
02.txt |
AC |
4 ms |
4352 KB |
03.txt |
AC |
4 ms |
4352 KB |
04.txt |
AC |
4 ms |
4352 KB |
05.txt |
AC |
4 ms |
4352 KB |
06.txt |
AC |
4 ms |
4352 KB |
07.txt |
AC |
3 ms |
4352 KB |
08.txt |
AC |
3 ms |
4352 KB |
09.txt |
AC |
3 ms |
4352 KB |
10.txt |
AC |
3 ms |
4352 KB |
11.txt |
AC |
3 ms |
4352 KB |
12.txt |
AC |
3 ms |
4352 KB |
13.txt |
AC |
3 ms |
4352 KB |
14.txt |
AC |
3 ms |
4352 KB |
15.txt |
AC |
3 ms |
4352 KB |
16.txt |
AC |
3 ms |
4352 KB |
17.txt |
AC |
3 ms |
4352 KB |
18.txt |
AC |
3 ms |
4352 KB |
19.txt |
AC |
2 ms |
4352 KB |
20.txt |
AC |
2 ms |
4352 KB |
21.txt |
AC |
2 ms |
4352 KB |
22.txt |
AC |
2 ms |
4352 KB |
s1.txt |
AC |
2 ms |
4352 KB |
s2.txt |
AC |
2 ms |
4352 KB |
s3.txt |
AC |
2 ms |
4352 KB |