Submission #11675808
Source Code Expand
// SNIPPET read
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())
}
}
impl Readable for i8 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<i8, String> {
use std::str::FromStr;
i8::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as i8", words[0])
})
}
}
impl Readable for u8 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<u8, String> {
use std::str::FromStr;
u8::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as u8", words[0])
})
}
}
impl Readable for i16 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<i16, String> {
use std::str::FromStr;
i16::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as i16", words[0])
})
}
}
impl Readable for u16 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<u16, String> {
use std::str::FromStr;
u16::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as u16", words[0])
})
}
}
impl Readable for i32 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<i32, String> {
use std::str::FromStr;
i32::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as i32", words[0])
})
}
}
impl Readable for u32 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<u32, String> {
use std::str::FromStr;
u32::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as u32", words[0])
})
}
}
impl Readable for i64 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<i64, String> {
use std::str::FromStr;
i64::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as i64", words[0])
})
}
}
impl Readable for u64 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<u64, String> {
use std::str::FromStr;
u64::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as u64", words[0])
})
}
}
impl Readable for isize {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<isize, String> {
use std::str::FromStr;
<isize>::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as isize", words[0])
})
}
}
impl Readable for usize {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<usize, String> {
use std::str::FromStr;
<usize>::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as usize", words[0])
})
}
}
impl Readable for f32 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<f32, String> {
use std::str::FromStr;
f32::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as f32", words[0])
})
}
}
impl Readable for f64 {
type Output = Self;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<f64, String> {
use std::str::FromStr;
f64::from_str(words[0]).map_err(|_| {
format!("cannot parse `{}` as f64", words[0])
})
}
}
#[allow(non_camel_case_types)]
pub struct u8_;
impl Readable for u8_ {
type Output = u8;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
u8::read_words(words).map(|n| n-1)
}
}
#[allow(non_camel_case_types)]
pub struct u16_;
impl Readable for u16_ {
type Output = u16;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
u16::read_words(words).map(|n| n-1)
}
}
#[allow(non_camel_case_types)]
pub struct u32_;
impl Readable for u32_ {
type Output = u32;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
u32::read_words(words).map(|n| n-1)
}
}
#[allow(non_camel_case_types)]
pub struct u64_;
impl Readable for u64_ {
type Output = u64;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
u64::read_words(words).map(|n| n-1)
}
}
#[allow(non_camel_case_types)]
pub struct usize_;
impl Readable for usize_ {
type Output = usize;
fn words_count() -> usize { 1 }
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
<usize>::read_words(words).map(|n| n-1)
}
}
impl<T1: Readable, T2: Readable> Readable for (T1, T2) {
type Output = (T1::Output, T2::Output);
fn words_count() -> usize {
T1::words_count() + T2::words_count()
}
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
assert_eq!(words.len(), Self::words_count());
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let val2 = T2::read_words(&words[start..])?;
Ok((val1, val2))
}
}
impl<T1: Readable, T2: Readable, T3: Readable> Readable for (T1, T2, T3) {
type Output = (T1::Output, T2::Output, T3::Output);
fn words_count() -> usize {
T1::words_count() + T2::words_count() + T3::words_count()
}
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
assert_eq!(words.len(), Self::words_count());
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let count2 = T2::words_count();
let val2 = T2::read_words(&words[start .. start+count2])?;
start += count2;
let val3 = T3::read_words(&words[start..])?;
Ok((val1, val2, val3))
}
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable> Readable for (T1, T2, T3, T4) {
type Output = (T1::Output, T2::Output, T3::Output, T4::Output);
fn words_count() -> usize {
T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count()
}
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
assert_eq!(words.len(), Self::words_count());
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let count2 = T2::words_count();
let val2 = T2::read_words(&words[start .. start+count2])?;
start += count2;
let count3 = T3::words_count();
let val3 = T3::read_words(&words[start .. start+count3])?;
start += count3;
let val4 = T4::read_words(&words[start..])?;
Ok((val1, val2, val3, val4))
}
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, T5: Readable> Readable for (T1, T2, T3, T4, T5) {
type Output = (T1::Output, T2::Output, T3::Output, T4::Output, T5::Output);
fn words_count() -> usize {
T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count() + T5::words_count()
}
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
assert_eq!(words.len(), Self::words_count());
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let count2 = T2::words_count();
let val2 = T2::read_words(&words[start .. start+count2])?;
start += count2;
let count3 = T3::words_count();
let val3 = T3::read_words(&words[start .. start+count3])?;
start += count3;
let count4 = T4::words_count();
let val4 = T4::read_words(&words[start .. start+count4])?;
start += count4;
let val5 = T5::read_words(&words[start..])?;
Ok((val1, val2, val3, val4, val5))
}
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, T5: Readable, T6: Readable> Readable for (T1, T2, T3, T4, T5, T6) {
type Output = (T1::Output, T2::Output, T3::Output, T4::Output, T5::Output, T6::Output);
fn words_count() -> usize {
T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count() + T5::words_count() + T6::words_count()
}
fn read_words(words: &[&str]) -> Result<Self::Output, String> {
assert_eq!(words.len(), Self::words_count());
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let count2 = T2::words_count();
let val2 = T2::read_words(&words[start .. start+count2])?;
start += count2;
let count3 = T3::words_count();
let val3 = T3::read_words(&words[start .. start+count3])?;
start += count3;
let count4 = T4::words_count();
let val4 = T4::read_words(&words[start .. start+count4])?;
start += count4;
let count5 = T5::words_count();
let val5 = T5::read_words(&words[start .. start+count5])?;
start += count5;
let val6 = T6::read_words(&words[start..])?;
Ok((val1, val2, val3, val4, val5, val6))
}
}
pub trait ReadableFromLine {
type Output;
fn read_line(line: &str) -> Result<Self::Output, String>;
}
fn split_into_words(line: &str) -> Vec<&str> {
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)
}
}
pub fn read_words_into_vec<T: Readable>(words: &[&str], line: &str) -> Result<Vec<T::Output>, String> {
let n = T::words_count();
assert_eq!(words.len() % n, 0);
let mut result = Vec::new();
for chunk in words.chunks(n) {
match T::read_words(chunk) {
Ok(v) => result.push(v),
Err(msg) => {
let fragment_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 `{}`: {}", fragment_msg, line, msg
));
}
}
}
Ok(result)
}
pub fn split_into_words_for_collection<T: Readable>(
line: &str, prefix_words_count: usize
) -> Result<Vec<&str>, String> {
let n = T::words_count();
let words = split_into_words(line);
if words.len() < prefix_words_count {
return Err(
format!("line `{}` has {} words, expected at least {}",
line, words.len(), prefix_words_count)
);
}
if (words.len() - prefix_words_count) % T::words_count() != 0 {
return Err(
format!("line `{}` has {} words, expected {} + {}",
line, words.len(), prefix_words_count, n)
);
}
Ok(words)
}
#[macro_export]
macro_rules! readable_collection {
($u:ident => $collection_in:ty, $collection_out:ty) => {
readable_collection!($u: [] => $collection_in, $collection_out);
};
($u:ident : [ $( $bound:path ),* ] => $collection_in:ty, $collection_out:ty) => {
impl<$u: Readable> ReadableFromLine for $collection_in
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = $collection_out;
fn read_line(line: &str) -> Result<Self::Output, String> {
let words = split_into_words_for_collection::<$u>(line, 0)?;
Ok(read_words_into_vec::<$u>(&words, line)?.into_iter().collect())
}
}
impl<T1: Readable, $u: Readable> ReadableFromLine for (T1, $collection_in)
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = (T1::Output, $collection_out);
fn read_line(line: &str) -> Result<Self::Output, String> {
let prefix_len = T1::words_count();
let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
let val1 = T1::read_words(&words[..prefix_len])?;
let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
Ok((val1, rest.into_iter().collect()))
}
}
impl<T1: Readable, T2: Readable, $u: Readable> ReadableFromLine for (T1, T2, $collection_in)
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = (T1::Output, T2::Output, $collection_out);
fn read_line(line: &str) -> Result<Self::Output, String> {
let prefix_len = <(T1, T2)>::words_count();
let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let count2 = T2::words_count();
let val2 = T2::read_words(&words[start .. start+count2])?;
let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
Ok((val1, val2, rest.into_iter().collect()))
}
}
impl<T1: Readable, T2: Readable, T3: Readable, $u: Readable> ReadableFromLine for (T1, T2, T3, $collection_in)
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = (T1::Output, T2::Output, T3::Output, $collection_out);
fn read_line(line: &str) -> Result<Self::Output, String> {
let prefix_len = <(T1, T2, T3)>::words_count();
let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let count2 = T2::words_count();
let val2 = T2::read_words(&words[start .. start+count2])?;
start += count2;
let count3 = T3::words_count();
let val3 = T3::read_words(&words[start .. start+count3])?;
let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
Ok((val1, val2, val3, rest.into_iter().collect()))
}
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, $u: Readable> ReadableFromLine for (T1, T2, T3, T4, $collection_in)
where
<$u as Readable>::Output: Sized $(+ $bound)*
{
type Output = (T1::Output, T2::Output, T3::Output, T4::Output, $collection_out);
fn read_line(line: &str) -> Result<Self::Output, String> {
let prefix_len = <(T1, T2, T3, T4)>::words_count();
let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
let mut start = 0;
let count1 = T1::words_count();
let val1 = T1::read_words(&words[start .. start+count1])?;
start += count1;
let count2 = T2::words_count();
let val2 = T2::read_words(&words[start .. start+count2])?;
start += count2;
let count3 = T3::words_count();
let val3 = T3::read_words(&words[start .. start+count3])?;
start += count3;
let count4 = T4::words_count();
let val4 = T4::read_words(&words[start .. start+count4])?;
let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
Ok((val1, val2, val3, val4, rest.into_iter().collect()))
}
}
};
}
readable_collection!(U => Vec<U>, Vec<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),*));
};
}
pub trait ReadableFromChunk {
type Output;
fn lines_count() -> usize;
fn read_chunk(lines: &[String]) -> Result<Self::Output, String>;
}
impl<T1: ReadableFromLine, T2: ReadableFromLine> ReadableFromChunk for (T1, T2) {
type Output = (T1::Output, T2::Output);
fn lines_count() -> usize { 2 }
fn read_chunk(lines: &[String]) -> Result<Self::Output, String> {
let out1 = T1::read_line(&lines[0])?;
let out2 = T2::read_line(&lines[1])?;
Ok((out1, out2))
}
}
impl<T1: ReadableFromLine, T2: ReadableFromLine, T3: ReadableFromLine> ReadableFromChunk for (T1, T2, T3) {
type Output = (T1::Output, T2::Output, T3::Output);
fn lines_count() -> usize { 3 }
fn read_chunk(lines: &[String]) -> Result<Self::Output, String> {
let out1 = T1::read_line(&lines[0])?;
let out2 = T2::read_line(&lines[1])?;
let out3 = T3::read_line(&lines[2])?;
Ok((out1, out2, out3))
}
}
impl<T1: ReadableFromLine, T2: ReadableFromLine, T3: ReadableFromLine, T4: ReadableFromLine> ReadableFromChunk for (T1, T2, T3, T4) {
type Output = (T1::Output, T2::Output, T3::Output, T4::Output);
fn lines_count() -> usize { 4 }
fn read_chunk(lines: &[String]) -> Result<Self::Output, String> {
let out1 = T1::read_line(&lines[0])?;
let out2 = T2::read_line(&lines[1])?;
let out3 = T3::read_line(&lines[2])?;
let out4 = T4::read_line(&lines[3])?;
Ok((out1, out2, out3, out4))
}
}
pub fn read_chunk<T: ReadableFromChunk>() -> T::Output {
let stdin = std::io::stdin();
let mut handle = stdin.lock();
read_chunk_from_handle::<T>(&mut handle).unwrap()
}
fn read_chunk_from_handle<T: ReadableFromChunk>(handle: &mut std::io::StdinLock) -> Option<T::Output> {
use std::io::BufRead;
let mut lines = vec![String::new(); T::lines_count()];
let mut first = true;
for line in &mut lines {
if handle.read_line(line).unwrap() == 0 && first {
return None;
}
first = false;
}
Some(T::read_chunk(&lines).unwrap())
}
#[macro_export]
macro_rules! read_chunk {
( $( $pat:pat = $t:ty ),+ ) => {
let ($($pat),+) = read_chunk::<($($t),+)>();
};
}
pub struct ReadLines<T: ReadableFromLine> {
phantom: std::marker::PhantomData<T>
}
impl<T: ReadableFromLine> Iterator for ReadLines<T> {
type Item = T::Output;
fn next(&mut self) -> Option<T::Output> {
use std::io::BufRead;
let stdin = std::io::stdin();
let mut line = String::new();
if stdin.lock().read_line(&mut line).unwrap() > 0 {
Some(T::read_line(&line).unwrap())
} else {
None
}
}
}
pub fn read_lines<T: ReadableFromLine>() -> ReadLines<T> {
ReadLines {
phantom: std::marker::PhantomData::<T>
}
}
pub struct ReadChunks<T: ReadableFromChunk> {
phantom: std::marker::PhantomData<T>
}
impl<T: ReadableFromChunk> Iterator for ReadChunks<T> {
type Item = T::Output;
fn next(&mut self) -> Option<T::Output> {
let stdin = std::io::stdin();
let mut handle = stdin.lock();
read_chunk_from_handle::<T>(&mut handle)
}
}
pub fn read_chunks<T: ReadableFromChunk>() -> ReadChunks<T> {
ReadChunks {
phantom: std::marker::PhantomData::<T>
}
}
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()
}
}
// SNIPPET utils
pub fn yn(result: bool) {
if result {
println!("Yes");
} else {
println!("No");
}
}
#[allow(non_snake_case)]
pub fn YN(result: bool) {
if result {
println!("YES");
} else {
println!("NO");
}
}
pub fn exit<T: std::fmt::Display>(msg: T) -> ! {
println!("{}", msg);
std::process::exit(0)
}
#[macro_export]
#[cfg(local)]
macro_rules! dbg {
() => {
{
use std::io::{self, Write};
writeln!(io::stderr(), "{}: dbg", line!()).unwrap();
}
};
($e: expr) => {
{
use std::io::{self, Write};
let result = $e;
writeln!(io::stderr(), "{}: {} = {:?}",
line!(), stringify!($e), result)
.unwrap();
result
}
}
}
#[macro_export]
#[cfg(not(local))]
macro_rules! dbg {
() => {};
($e: expr) => {
{ $e }
}
}
// SNIPPET option
pub trait BoolExt {
fn then<T>(self, value: T) -> Option<T>;
fn then_with<T, F>(self, f: F) -> Option<T> where F: FnOnce() -> T;
fn and<T>(self, option: Option<T>) -> Option<T>;
fn and_then<T, F>(self, f: F) -> Option<T> where F: FnOnce() -> Option<T>;
}
impl BoolExt for bool {
fn then<T>(self, value: T) -> Option<T> {
if self { Some(value) } else { None }
}
fn then_with<T, F>(self, f: F) -> Option<T> where F: FnOnce() -> T {
if self { Some(f()) } else { None }
}
fn and<T>(self, option: Option<T>) -> Option<T> {
if self { option } else { None }
}
fn and_then<T, F>(self, f: F) -> Option<T> where F: FnOnce() -> Option<T> {
if self { f() } else { None }
}
}
pub trait OptionExt<T> {
fn to_string_or<U: std::fmt::Display>(&self, default: U) -> String
where
T: std::fmt::Display;
}
impl<T> OptionExt<T> for Option<T> {
fn to_string_or<U: std::fmt::Display>(&self, default: U) -> String
where
T: std::fmt::Display
{
self.as_ref().map(|x| x.to_string()).unwrap_or(default.to_string())
}
/*
fn get_or_insert_with<F: FnOnce() -> T>(&mut self, f: F) -> &mut T {
match *self {
None => *self = Some(f()),
_ => ()
}
self.as_mut().unwrap()
}
*/
}
pub trait Guard: Sized {
fn guard<F: FnOnce(&Self) -> bool>(self, pred: F) -> Option<Self>;
}
impl<T> Guard for T {
fn guard<F: FnOnce(&T) -> bool>(self, pred: F) -> Option<T> {
if pred(&self) { Some(self) } else { None }
}
}
// SNIPPET iter
#[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)
}
}
}
pub struct Chunks<I: Iterator> {
iter: I,
size: usize
}
impl<I: Iterator> Iterator for Chunks<I> {
type Item = Vec<I::Item>;
fn next(&mut self) -> Option<Self::Item> {
let first = self.iter.next();
if first.is_none() {
return None;
}
let mut chunk = Vec::with_capacity(self.size);
chunk.push(first.unwrap());
for _ in 0..self.size-1 {
match self.iter.next() {
Some(x) => chunk.push(x),
None => break
}
}
Some(chunk)
}
}
#[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())
}
}
}
}
/*
impl<I, J> DoubleEndedIterator for Flatten<I>
where
I: DoubleEndedIterator,
J: DoubleEndedIterator,
I::Item: J {}
*/
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 struct RunLength<I: Iterator> {
cur: Option<I::Item>,
iter: I
}
impl<I: Iterator> Iterator for RunLength<I> where I::Item: Eq {
type Item = (I::Item, usize);
fn next(&mut self) -> Option<(I::Item, usize)> {
let cur = self.cur.take();
cur.map(|value| {
let mut length = 1;
loop {
let next = self.iter.next();
match next {
Some(next_value) => {
if value == next_value {
length += 1;
} else {
self.cur = Some(next_value);
break;
}
}
None => {
self.cur = None;
break;
}
}
}
(value, length)
})
}
}
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 chunks(self, size: usize) -> Chunks<Self> where Self: Sized {
assert!(size > 0);
Chunks {
iter: self,
size: size
}
}
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 lscan1<F>(mut self, f: F) -> Option<LScan<Self, Self::Item, F>>
where
Self: Sized,
Self::Item: Clone,
F: FnMut(&Self::Item, Self::Item) -> Self::Item
{
self.next().map(|first| self.lscan(first, 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 run_length(mut self) -> RunLength<Self> where Self: Sized, Self::Item: Eq {
RunLength {
cur: self.next(),
iter: self
}
}
fn join<T: std::fmt::Display>(mut self, sep: T) -> 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 trait IteratorInnerProduct<T, Rhs=T>: ExactSizeIterator<Item=T> {
fn inner_product<I, J>(self, other: I) -> Option<<T as std::ops::Mul<Rhs>>::Output>
where
Self: Sized,
I: IntoIterator<Item=Rhs, IntoIter=J>,
J: Iterator<Item=Rhs> + ExactSizeIterator,
T: std::ops::Mul<Rhs>,
<T as std::ops::Mul<Rhs>>::Output: std::iter::Sum
{
let iter = other.into_iter();
(self.len() == iter.len()).then_with(|| {
self.zip(iter).map(|(a, b)| a * b).sum()
})
}
}
impl<T1, T2, I> IteratorInnerProduct<T1, T2> for I
where
I: Iterator<Item=T1> + ExactSizeIterator,
T1: std::ops::Mul<T2>
{}
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 }
}
// SNIPPET int
pub trait PrimitiveInteger:
Sized + Ord +
std::ops::Add<Output=Self> +
std::ops::Sub<Output=Self> +
std::ops::Div<Output=Self>
{
fn one() -> Self;
fn abs_diff(self, rhs: Self) -> Self;
fn rem_euclid(self, rhs: Self) -> Self;
}
macro_rules! impl_primitive_integer {
( $($t: ty)* ) => { $(
impl PrimitiveInteger for $t {
fn one() -> $t {
1
}
fn abs_diff(self, rhs: $t) -> $t {
if self < rhs { rhs - self } else { self - rhs }
}
#[allow(unused_comparisons)]
fn rem_euclid(self, rhs: $t) -> $t {
let r = self % rhs;
if r < 0 {
if rhs < 0 { r - rhs } else { r + rhs }
} else {
r
}
}
}
)* }
}
impl_primitive_integer!(u8 u16 u32 u64 usize i8 i16 i32 i64 isize);
pub trait PrimitiveUnsigned: PrimitiveInteger {
fn ceil_div(self, rhs: Self) -> Self;
fn round_div(self, rhs: Self) -> Self;
fn log2(self) -> Option<Self>;
fn ceil_log2(self) -> Option<Self>;
fn sqrt(self) -> Self;
}
macro_rules! impl_primitive_unsigned {
( $($t: ty)* ) => { $(
impl PrimitiveUnsigned for $t {
fn ceil_div(self, rhs: $t) -> $t {
(self + rhs - 1) / rhs
}
fn round_div(self, rhs: $t) -> $t {
(self + rhs/2) / rhs
}
fn log2(mut self) -> Option<$t> {
if self == 0 {
None
} else {
let mut ans = 0;
while self > 1 {
ans += 1;
self /= 2;
}
Some(ans)
}
}
fn ceil_log2(self) -> Option<$t> {
self.log2().map(|x| {
(self + ((1<<x) - 1)).log2().unwrap()
})
}
fn sqrt(self) -> $t {
(self as f64).sqrt() as $t
}
}
)* }
}
impl_primitive_unsigned!(u8 u16 u32 u64 usize);
pub fn gcd(a: u64, b: u64) -> u64 {
if b == 0 { a } else { gcd(b, a%b) }
}
pub fn bezout(a: i64, b: i64) -> (i64, i64, u64) {
let (x, y, g) = bezout_sub((a * a.signum()) as u64, (b * b.signum()) as u64);
(x * a.signum(), y * b.signum(), g)
}
fn bezout_sub(a: u64, b: u64) -> (i64, i64, u64) {
if b == 0 { (1, 0, a) } else {
let m = (a / b) as i64;
let (x, y, g) = bezout_sub(b, a%b);
(y, x - m*y, g)
}
}
// SNIPPET cmp
use std::cmp::{Ord, Ordering};
pub fn minmax<T: Ord>(a: T, b: T) -> (T, T) {
if a <= b { (a, b) } else { (b, a) }
}
#[macro_export]
macro_rules! chmin {
($place: expr, $expr: expr) => {
let value = $expr;
if value < $place {
$place = value;
}
}
}
#[macro_export]
macro_rules! chmax {
($place: expr, $expr: expr) => {
let value = $expr;
if value > $place {
$place = value;
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default, Hash)]
pub struct Reverse<T: Ord>(pub T);
impl<T: Ord> PartialOrd for Reverse<T> {
fn partial_cmp(&self, other: &Reverse<T>) -> Option<Ordering> {
other.0.partial_cmp(&self.0)
}
}
impl<T: Ord> Ord for Reverse<T> {
fn cmp(&self, other: &Reverse<T>) -> Ordering {
other.0.cmp(&self.0)
}
}
pub trait SortDesc<T> {
fn sort_desc(&mut self) where T: Ord;
fn sort_desc_by_key<K: Ord, F: FnMut(&T) -> K>(&mut self, f: F);
}
impl<T> SortDesc<T> for [T] {
fn sort_desc(&mut self) where T: Ord {
self.sort();
self.reverse();
}
fn sort_desc_by_key<K: Ord, F: FnMut(&T) -> K>(&mut self, mut f: F) {
self.sort_by_key(|x| Reverse(f(x)));
}
}
#[derive(Clone, Copy, PartialEq, PartialOrd, Debug, Default, Hash)]
pub struct Total<T: PartialOrd + PartialEq>(pub T);
impl<T: PartialOrd + PartialEq> Eq for Total<T> {}
impl<T: PartialOrd + PartialEq> Ord for Total<T> {
fn cmp(&self, other: &Self) -> Ordering {
self.partial_cmp(other).unwrap()
}
}
pub trait IteratorMinmax: Iterator {
fn minmax(self) -> Option<(Self::Item, Self::Item)>;
fn minmax_by_key<K, F>(self, key_fn: F) -> Option<(Self::Item, Self::Item)>
where
K: Ord,
F: FnMut(&Self::Item) -> K;
fn minmax_by<F>(self, compare: F) -> Option<(Self::Item, Self::Item)>
where
F: FnMut(&Self::Item, &Self::Item) -> Ordering;
}
impl<T: Ord + Clone, I: Iterator<Item=T>> IteratorMinmax for I {
fn minmax(self) -> Option<(Self::Item, Self::Item)> {
self.minmax_by(|a, b| a.cmp(b))
}
fn minmax_by_key<K, F>(self, mut key_fn: F) -> Option<(Self::Item, Self::Item)>
where
K: Ord,
F: FnMut(&Self::Item) -> K
{
self.minmax_by(|a, b| key_fn(a).cmp(&key_fn(b)))
}
fn minmax_by<F>(mut self, mut compare: F) -> Option<(Self::Item, Self::Item)>
where
F: FnMut(&Self::Item, &Self::Item) -> Ordering
{
let first = match self.next() {
Some(x) => x,
None => return None
};
let second = match self.next() {
Some(x) => x,
None => return Some((first.clone(), first))
};
let mut result = minmax(first, second);
while let Some(x) = self.next() {
let (min, max) = result;
result = if compare(&x, &min) == Ordering::Less {
(x, max)
} else if compare(&max, &x) == Ordering::Less {
(min, x)
} else {
(min, max)
};
}
Some(result)
}
}
// END SNIPPETS
// Here is the documentation: https://yoshrc.github.io/rust-atcoder-snippets/atcoder_snippets/index.html
use std::cmp;
fn choose(n: u64, m: u64) -> u64 {
let mut numer: Vec<u64> = (1..n+1).rev().take(m as usize).collect();
for mut x in 1..m+1 {
for n in &mut numer {
if x == 1 {
break;
}
let g = gcd(x, *n);
*n /= g;
x /= g;
}
}
numer.into_iter().product()
}
fn main() {
read!(n = usize, a = usize, b = usize);
read!(mut vs = Vec<u64>);
vs.sort_desc();
let ave = vs.iter().take(a).map(|&x| x as f64).sum::<f64>() / a as f64;
let counts: Vec<usize> = vs.iter().run_length().map(|(_, c)| c).collect();
let mut prefsums: Vec<usize> = counts.iter()
.lscan(0, |&acc, &next| acc + next)
.collect();
prefsums.push(n+1);
let i = prefsums.windows(2).position(|w| w[0] <= a && a < w[1]).unwrap();
let count: u64 = if i == 0 {
let max = cmp::min(b, counts[0]);
(a..max+1).map(|c| choose(counts[0] as u64, c as u64)).sum()
} else {
choose(counts[i] as u64, (a - prefsums[i]) as u64)
};
println!("{}\n{}", ave, count);
}
Submission Info
Submission Time |
|
Task |
D - Maximum Average Sets |
User |
avtomat |
Language |
Rust (1.15.1) |
Score |
400 |
Code Size |
39886 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
4352 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
4352 KB |
sample_02.txt |
AC |
2 ms |
4352 KB |
sample_03.txt |
AC |
2 ms |
4352 KB |
sample_04.txt |
AC |
2 ms |
4352 KB |
subtask_1_1.txt |
AC |
2 ms |
4352 KB |
subtask_1_10.txt |
AC |
2 ms |
4352 KB |
subtask_1_11.txt |
AC |
2 ms |
4352 KB |
subtask_1_12.txt |
AC |
2 ms |
4352 KB |
subtask_1_13.txt |
AC |
2 ms |
4352 KB |
subtask_1_14.txt |
AC |
2 ms |
4352 KB |
subtask_1_15.txt |
AC |
2 ms |
4352 KB |
subtask_1_2.txt |
AC |
2 ms |
4352 KB |
subtask_1_3.txt |
AC |
2 ms |
4352 KB |
subtask_1_4.txt |
AC |
2 ms |
4352 KB |
subtask_1_5.txt |
AC |
2 ms |
4352 KB |
subtask_1_6.txt |
AC |
2 ms |
4352 KB |
subtask_1_7.txt |
AC |
2 ms |
4352 KB |
subtask_1_8.txt |
AC |
2 ms |
4352 KB |
subtask_1_9.txt |
AC |
2 ms |
4352 KB |