結果
問題 | No.919 You Are A Project Manager |
ユーザー | ngtkana |
提出日時 | 2022-01-02 10:22:23 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 256 ms / 3,000 ms |
コード長 | 27,853 bytes |
コンパイル時間 | 15,553 ms |
コンパイル使用メモリ | 378,208 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 07:56:43 |
合計ジャッジ時間 | 22,755 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 198 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 37 ms
5,248 KB |
testcase_05 | AC | 40 ms
5,248 KB |
testcase_06 | AC | 5 ms
5,248 KB |
testcase_07 | AC | 97 ms
5,248 KB |
testcase_08 | AC | 22 ms
5,248 KB |
testcase_09 | AC | 15 ms
5,248 KB |
testcase_10 | AC | 28 ms
5,248 KB |
testcase_11 | AC | 27 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 35 ms
5,248 KB |
testcase_14 | AC | 3 ms
5,248 KB |
testcase_15 | AC | 11 ms
5,248 KB |
testcase_16 | AC | 51 ms
5,248 KB |
testcase_17 | AC | 190 ms
5,248 KB |
testcase_18 | AC | 198 ms
5,248 KB |
testcase_19 | AC | 196 ms
5,248 KB |
testcase_20 | AC | 226 ms
5,248 KB |
testcase_21 | AC | 199 ms
5,248 KB |
testcase_22 | AC | 107 ms
5,248 KB |
testcase_23 | AC | 106 ms
5,248 KB |
testcase_24 | AC | 111 ms
5,248 KB |
testcase_25 | AC | 107 ms
5,248 KB |
testcase_26 | AC | 226 ms
5,248 KB |
testcase_27 | AC | 193 ms
5,248 KB |
testcase_28 | AC | 244 ms
5,248 KB |
testcase_29 | AC | 190 ms
5,248 KB |
testcase_30 | AC | 191 ms
5,248 KB |
testcase_31 | AC | 187 ms
5,248 KB |
testcase_32 | AC | 187 ms
5,248 KB |
testcase_33 | AC | 117 ms
5,248 KB |
testcase_34 | AC | 116 ms
5,248 KB |
testcase_35 | AC | 256 ms
5,248 KB |
testcase_36 | AC | 250 ms
5,248 KB |
testcase_37 | AC | 250 ms
5,248 KB |
testcase_38 | AC | 249 ms
5,248 KB |
testcase_39 | AC | 1 ms
5,248 KB |
testcase_40 | AC | 11 ms
5,248 KB |
testcase_41 | AC | 4 ms
5,248 KB |
testcase_42 | AC | 4 ms
5,248 KB |
testcase_43 | AC | 7 ms
5,248 KB |
testcase_44 | AC | 15 ms
5,248 KB |
testcase_45 | AC | 4 ms
5,248 KB |
testcase_46 | AC | 13 ms
5,248 KB |
testcase_47 | AC | 105 ms
5,248 KB |
testcase_48 | AC | 105 ms
5,248 KB |
testcase_49 | AC | 113 ms
5,248 KB |
testcase_50 | AC | 107 ms
5,248 KB |
testcase_51 | AC | 98 ms
5,248 KB |
testcase_52 | AC | 72 ms
5,248 KB |
testcase_53 | AC | 95 ms
5,248 KB |
testcase_54 | AC | 11 ms
5,248 KB |
testcase_55 | AC | 1 ms
5,248 KB |
testcase_56 | AC | 1 ms
5,248 KB |
testcase_57 | AC | 1 ms
5,248 KB |
コンパイルメッセージ
warning: unused imports: `Leaf`, `Tuple`, `VecLen` --> src/main.rs:566:27 | 566 | multi_token::{Leaf, Parser, ParserTuple, RawTuple, Tuple, VecLen}, | ^^^^ ^^^^^ ^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `with_str` --> src/main.rs:804:35 | 804 | pub use self::i::{with_stdin, with_str}; | ^^^^^^^^ warning: unused imports: `ParserTuple`, `Parser`, `RawTuple`, `Token`, `Usize1` --> src/main.rs:806:28 | 806 | pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1}; | ^^^^^^ ^^^^^^^^^^^ ^^^^^^^^ ^^^^^ ^^^^^^
ソースコード
use std::{ isize::MIN, iter::{once, FromIterator}, }; #[allow(unused_imports)] #[cfg(feature = "dbg")] use dbg::lg; use wavelet_matrix::WaveletMatrix; fn main() { let mut buf = ngtio::with_stdin(); let n = buf.usize(); let a = buf.vec::<isize>(n); let shift = 1_000_000_000; let wm = WaveletMatrix::from_iter(a.iter().map(|&x| (x + shift) as usize)); let mut ans = MIN; for k in 1..=n { let mut front = once(0) .chain((0..=n - k).step_by(k).map(|l| median(&wm, shift, l, l + k))) .collect::<Vec<_>>(); let mut back = once(0) .chain( (0..=n - k) .rev() .step_by(k) .map(|l| median(&wm, shift, l, l + k)), ) .collect::<Vec<_>>(); accum::add(&mut front); accum::add(&mut back); accum::max(&mut front); accum::max(&mut back); ans = ans.max( front .iter() .rev() .zip(&back) .map(|(&x, &y)| x + y) .max() .unwrap() * k as isize, ); } println!("{}", ans); } fn median(wm: &WaveletMatrix, shift: isize, l: usize, r: usize) -> isize { wm.quantile((r - l - 1) / 2, l..r, ..).unwrap() as isize - shift } // accum {{{ #[allow(dead_code)] mod accum { use std::{ cmp::Ord, ops::{ AddAssign, BitAndAssign, BitOrAssign, BitXorAssign, DivAssign, MulAssign, SubAssign, }, }; pub fn add<T: Copy + AddAssign>(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y += x); } pub fn add_inv<T: Copy + SubAssign>(a: &mut [T]) { rfor_each_mut(a, |&mut x, y| *y -= x); } pub fn mul<T: Copy + MulAssign>(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y *= x); } pub fn mul_inv<T: Copy + DivAssign>(a: &mut [T]) { rfor_each_mut(a, |&mut x, y| *y /= x); } // -- ord pub fn min<T: Copy + Ord>(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y = x.min(*y)); } pub fn max<T: Copy + Ord>(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y = x.max(*y)); } pub fn skipped_min<T: Copy + Ord>(a: &[T], max: T) -> Vec<T> { skipped(a, |x, y| (*x).min(*y), || max).collect() } pub fn skipped_max<T: Copy + Ord>(a: &[T], min: T) -> Vec<T> { skipped(a, |x, y| (*x).max(*y), || min).collect() } // -- bit pub fn xor<T: Copy + BitXorAssign>(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y ^= x); } pub fn xor_inv<T: Copy + BitXorAssign>(a: &mut [T]) { rfor_each_mut(a, |&mut x, y| *y ^= x); } pub fn or<T: Copy + BitOrAssign>(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y |= x); } pub fn and<T: Copy + BitAndAssign>(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y &= x); } // -- for_each pub fn for_each<T>(a: &[T], mut f: impl FnMut(&T, &T)) { if !a.is_empty() { for i in 1..a.len() { let (left, right) = a.split_at(i); f(left.last().unwrap(), right.first().unwrap()); } } } pub fn rfor_each<T>(a: &[T], mut f: impl FnMut(&T, &T)) { if !a.is_empty() { for i in (1..a.len()).rev() { let (left, right) = a.split_at(i); f(left.last().unwrap(), right.first().unwrap()); } } } pub fn for_each_mut<T>(a: &mut [T], mut f: impl FnMut(&mut T, &mut T)) { if !a.is_empty() { for i in 1..a.len() { let (left, right) = a.split_at_mut(i); f(left.last_mut().unwrap(), right.first_mut().unwrap()); } } } pub fn rfor_each_mut<T>(a: &mut [T], mut f: impl FnMut(&mut T, &mut T)) { if !a.is_empty() { for i in (1..a.len()).rev() { let (left, right) = a.split_at_mut(i); f(left.last_mut().unwrap(), right.first_mut().unwrap()); } } } pub fn skipped<T, F, I>(a: &[T], f: F, identity: I) -> Skipped<T, F, I> where F: FnMut(&T, &T) -> T, I: FnMut() -> T, { Skipped::new(a, f, identity) } #[derive(Clone, Debug, Default, Hash, PartialEq)] pub struct Skipped<'a, T, F, I> { a: &'a [T], left: T, right: Vec<T>, f: F, identity: I, } impl<'a, T, F, I> Skipped<'a, T, F, I> where F: FnMut(&T, &T) -> T, I: FnMut() -> T, { fn new(a: &'a [T], mut f: F, mut identity: I) -> Self { let right = if a.is_empty() { Default::default() } else { let mut right = vec![identity()]; for x in a[1..].iter().rev() { let x = f(x, right.last().unwrap()); right.push(x); } right }; Self { a, left: identity(), right, f, identity, } } } impl<'a, T, F, I> Iterator for Skipped<'a, T, F, I> where F: FnMut(&T, &T) -> T, I: FnMut() -> T, { type Item = T; fn next(&mut self) -> Option<Self::Item> { if let Some(right) = self.right.pop() { let res = (self.f)(&self.left, &right); self.left = (self.f)(&self.left, &self.a[0]); self.a = &self.a[1..]; Some(res) } else { None } } } } // }}} // wavelet_matrix {{{ #[allow(dead_code)] mod wavelet_matrix { #![allow(clippy::len_zero)] use std::{ fmt::Debug, iter::FromIterator, mem::size_of, ops::{Bound, Range, RangeBounds}, }; const UNIT: usize = size_of::<usize>(); #[derive(Clone, Default, Hash, PartialEq)] pub struct WaveletMatrix { table: Vec<StaticBitVec>, } impl Debug for WaveletMatrix { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_list() .entries((0..self.len()).map(|i| self.access(i))) .finish() } } impl FromIterator<usize> for WaveletMatrix { fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self { let mut slice = iter.into_iter().map(Into::into).collect::<Vec<_>>(); Self::from_slice_of_usize_mut(&mut slice, |_| ()) } } impl WaveletMatrix { pub fn is_empty(&self) -> bool { self.table.is_empty() } pub fn len(&self) -> usize { self.table.first().map_or(0, |row| row.len()) } pub fn from_iter_collect_vec2( iter: impl IntoIterator<Item = usize>, ) -> (Self, Vec<Vec<usize>>) { let mut slice = iter.into_iter().map(Into::into).collect::<Vec<_>>(); let mut table = Vec::new(); let wm = Self::from_slice_of_usize_mut(&mut slice, |row| table.push(row.to_vec())); (wm, table) } pub fn from_slice_of_usize_mut( slice: &mut [usize], mut callback: impl FnMut(&[usize]), ) -> Self { let ht = slice.iter().copied().max().map_or(0, |value| { // 要素がすべて 0 のときにも構築してほしいので、 // 最低でも 1 の高さを持つようにします。 ((value + 1).next_power_of_two().trailing_zeros() as usize).max(1) }); let table = (0..ht) .rev() .map(|p| { callback(slice); let res = slice.iter().map(|&value| value >> p & 1 == 1).collect(); stable_partition_by_key(slice, |value| value >> p & 1 == 1); res }) .collect(); callback(slice); Self { table } } pub fn access(&self, mut i: usize) -> usize { assert!(i < self.table[0].len()); let mut ans = 0; for row in &self.table { let here = row.access(i); i = next_position(row, i, row.access(i)); ans <<= 1; ans |= here as usize; } ans } pub fn range_freq( &self, index: impl RangeBounds<usize>, value: impl RangeBounds<usize>, ) -> usize { self.spans(index, value).map(|span| span.index.len()).sum() } pub fn next_value( &self, index: impl RangeBounds<usize>, value: impl RangeBounds<usize>, ) -> Option<usize> { self.root(open(index, self.len())) .next_value(&open(value, self.lim())) } pub fn prev_value( &self, index: impl RangeBounds<usize>, value: impl RangeBounds<usize>, ) -> Option<usize> { self.root(open(index, self.len())) .prev_value(&open(value, self.lim())) } pub fn quantile( &self, k: usize, index: impl RangeBounds<usize>, value: impl RangeBounds<usize>, ) -> Option<usize> { self.root(open(index, self.len())) .quantile(k, &open(value, self.lim())) .ok() } pub fn spans( &self, index: impl RangeBounds<usize>, value: impl RangeBounds<usize>, ) -> Spans<'_> { let index = open(index, self.len()); let target = open(value, self.lim()); if target.len() == 0 { return Spans { stack: Vec::new(), target, }; } let mut current = self.root(index); let mut stack = Vec::new(); while !is_subrange_of(¤t.value, &target) { let left = current.left_down(); if is_disjoint_with(&left.value, &target) { current = current.right_down(); } else { stack.push(current); current = left; } } stack.push(current); Spans { stack, target } } fn lim(&self) -> usize { 1 << self.table.len() } fn root(&self, index: Range<usize>) -> SpanInNode<'_> { SpanInNode { wm: self, depth: 0, index, value: 0..self.lim(), } } } fn stable_partition_by_key(slice: &mut [usize], is_upper: impl Fn(usize) -> bool) -> usize { let mut upper = Vec::new(); let mut i = 0; for j in 0..slice.len() { if is_upper(slice[j]) { upper.push(slice[j]); } else { slice[i] = slice[j]; i += 1; } } slice[i..].copy_from_slice(&upper); i } fn next_position(row: &StaticBitVec, i: usize, which: bool) -> usize { match which { false => i - row.rank(i), true => row.len() - row.rank(row.len()) + row.rank(i), } } fn next_position_range(row: &StaticBitVec, range: &Range<usize>, which: bool) -> Range<usize> { next_position(row, range.start, which)..next_position(row, range.end, which) } #[derive(Clone, Debug, Default, Hash, PartialEq)] pub struct StaticBitVec { len: usize, rank: Vec<usize>, pattern: Vec<usize>, } impl FromIterator<bool> for StaticBitVec { fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self { let mut iter = iter.into_iter(); let mut rank = Vec::new(); let mut pattern = Vec::new(); let mut rank_c = 0; let mut pattern_c = 0; let mut len = 0; 'OUTER: loop { rank.push(rank_c); for i in 0..UNIT { match iter.next() { None => { pattern.push(pattern_c); break 'OUTER; } Some(false) => (), Some(true) => { pattern_c |= 1 << i; rank_c += 1; } } len += 1; } pattern.push(pattern_c); pattern_c = 0; } Self { len, rank, pattern } } } impl StaticBitVec { pub fn is_empty(&self) -> bool { self.len == 0 } pub fn len(&self) -> usize { self.len } pub fn access(&self, i: usize) -> bool { assert!(i < self.len); let (q, r) = divrem(i, UNIT); self.pattern[q] >> r & 1 == 1 } pub fn rank(&self, end: usize) -> usize { assert!(end <= self.len); let (q, r) = divrem(end, UNIT); self.rank[q] + (self.pattern[q] & ((1 << r) - 1)).count_ones() as usize } pub fn select(&self, target: usize) -> usize { if target == 0 { return 0; } let mut lr = 0..self.rank.len(); while 1 < lr.len() { let c = midpoint(&lr); *if self.rank[c] < target { &mut lr.start } else { &mut lr.end } = c; } let q = lr.start; let mut lr = 0..UNIT; while 1 < lr.len() { let c = midpoint(&lr); *if (self.rank[q] + (self.pattern[q] & ((1 << c) - 1)).count_ones() as usize) < target { &mut lr.start } else { &mut lr.end } = c; } q * UNIT + lr.end } } #[derive(Clone, Debug, Hash, PartialEq)] pub struct Spans<'a> { stack: Vec<SpanInNode<'a>>, target: Range<usize>, } impl<'a> Iterator for Spans<'a> { type Item = SpanInNode<'a>; fn next(&mut self) -> Option<Self::Item> { let ans = self.stack.pop()?; if ans.value.end == self.target.end { self.stack.clear(); } else { let prev = self.stack.pop().unwrap(); let mut next = prev.right_down(); self.stack.push(next.clone()); while !is_subrange_of(&next.value, &self.target) { next = next.left_down(); self.stack.push(next.clone()); } } Some(ans) } } #[derive(Clone, Debug, Hash, PartialEq)] pub struct SpanInNode<'a> { wm: &'a WaveletMatrix, pub depth: usize, pub index: Range<usize>, pub value: Range<usize>, } impl<'a> SpanInNode<'a> { fn left_down(&self) -> Self { Self { wm: self.wm, depth: self.depth + 1, index: next_position_range(&self.wm.table[self.depth], &self.index, false), value: self.value.start..midpoint(&self.value), } } fn right_down(&self) -> Self { Self { wm: self.wm, depth: self.depth + 1, index: next_position_range(&self.wm.table[self.depth], &self.index, true), value: midpoint(&self.value)..self.value.end, } } fn next_value(&self, target: &Range<usize>) -> Option<usize> { if is_disjoint_with(&self.value, target) || self.index.len() == 0 { None } else if self.value.len() == 1 { Some(self.value.start) } else { self.left_down() .next_value(target) .or_else(|| self.right_down().next_value(target)) } } fn prev_value(&self, target: &Range<usize>) -> Option<usize> { if is_disjoint_with(&self.value, target) || self.index.len() == 0 { None } else if self.value.len() == 1 { Some(self.value.start) } else { self.right_down() .prev_value(target) .or_else(|| self.left_down().prev_value(target)) } } fn quantile(&self, k: usize, target: &Range<usize>) -> Result<usize, usize> { let ans = if is_disjoint_with(&self.value, target) { Err(0) } else if is_subrange_of(&self.value, target) && self.index.len() <= k { Err(self.index.len()) } else if self.value.len() == 1 { Ok(self.value.start) } else { self.left_down().quantile(k, target).or_else(|len| { self.right_down() .quantile(k - len, target) .map_err(|e| e + len) }) }; ans } } fn midpoint(range: &Range<usize>) -> usize { range.start + (range.end - range.start) / 2 } fn is_disjoint_with(lhs: &Range<usize>, rhs: &Range<usize>) -> bool { lhs.end <= rhs.start || rhs.end <= lhs.start } fn is_subrange_of(lhs: &Range<usize>, rhs: &Range<usize>) -> bool { rhs.start <= lhs.start && lhs.end <= rhs.end } fn divrem(num: usize, den: usize) -> (usize, usize) { let q = num / den; (q, num - q * den) } fn open(range: impl RangeBounds<usize>, len: usize) -> Range<usize> { (match range.start_bound() { Bound::Included(&l) => l.min(len), Bound::Excluded(&l) => (l + 1).min(len), Bound::Unbounded => 0, })..(match range.end_bound() { Bound::Included(&r) => (r + 1).min(len), Bound::Excluded(&r) => r.min(len), Bound::Unbounded => len, }) } } // }}} // template {{{ #[cfg(not(feature = "dbg"))] #[allow(unused_macros)] #[macro_export] macro_rules! lg { ($($expr:expr),*) => {}; } #[allow(dead_code)] mod ngtio { mod i { pub use self::{ multi_token::{Leaf, Parser, ParserTuple, RawTuple, Tuple, VecLen}, token::{Token, Usize1}, }; use std::{ io::{self, BufRead}, iter, }; pub fn with_stdin() -> Tokenizer<io::BufReader<io::Stdin>> { io::BufReader::new(io::stdin()).tokenizer() } pub fn with_str(src: &str) -> Tokenizer<&[u8]> { src.as_bytes().tokenizer() } pub struct Tokenizer<S: BufRead> { queue: Vec<String>, // FIXME: String のみにすると速そうです。 scanner: S, } macro_rules! prim_method { ($name:ident: $T:ty) => { pub fn $name(&mut self) -> $T { <$T>::leaf().parse(self) } }; ($name:ident) => { prim_method!($name: $name); }; } macro_rules! prim_methods { ($name:ident: $T:ty; $($rest:tt)*) => { prim_method!($name:$T); prim_methods!($($rest)*); }; ($name:ident; $($rest:tt)*) => { prim_method!($name); prim_methods!($($rest)*); }; () => () } impl<S: BufRead> Tokenizer<S> { pub fn token(&mut self) -> String { self.load(); self.queue.pop().expect("入力が終了したのですが。") } pub fn new(scanner: S) -> Self { Self { queue: Vec::new(), scanner, } } fn load(&mut self) { while self.queue.is_empty() { let mut s = String::new(); let length = self.scanner.read_line(&mut s).unwrap(); // 入力が UTF-8 でないときにエラーだそうです。 if length == 0 { break; } self.queue = s.split_whitespace().rev().map(str::to_owned).collect(); } } pub fn skip_line(&mut self) { assert!( self.queue.is_empty(), "行の途中で呼ばないでいただきたいです。現在のトークンキュー: {:?}", &self.queue ); self.load(); } pub fn end(&mut self) { self.load(); assert!(self.queue.is_empty(), "入力はまだあります!"); } pub fn parse<T: Token>(&mut self) -> T::Output { T::parse(&self.token()) } pub fn parse_collect<T: Token, B>(&mut self, n: usize) -> B where B: iter::FromIterator<T::Output>, { iter::repeat_with(|| self.parse::<T>()).take(n).collect() } pub fn tuple<T: RawTuple>(&mut self) -> <T::LeafTuple as Parser>::Output { T::leaf_tuple().parse(self) } pub fn vec<T: Token>(&mut self, len: usize) -> Vec<T::Output> { T::leaf().vec(len).parse(self) } pub fn vec_tuple<T: RawTuple>( &mut self, len: usize, ) -> Vec<<T::LeafTuple as Parser>::Output> { T::leaf_tuple().vec(len).parse(self) } pub fn vec2<T: Token>(&mut self, height: usize, width: usize) -> Vec<Vec<T::Output>> { T::leaf().vec(width).vec(height).parse(self) } pub fn vec2_tuple<T>( &mut self, height: usize, width: usize, ) -> Vec<Vec<<T::LeafTuple as Parser>::Output>> where T: RawTuple, { T::leaf_tuple().vec(width).vec(height).parse(self) } prim_methods! { u8; u16; u32; u64; u128; usize; i8; i16; i32; i64; i128; isize; f32; f64; char; string: String; } } mod token { use super::multi_token::Leaf; use std::{any, fmt, marker, str}; pub trait Token: Sized { type Output; fn parse(s: &str) -> Self::Output; fn leaf() -> Leaf<Self> { Leaf(marker::PhantomData) } } impl<T> Token for T where T: str::FromStr, <Self as str::FromStr>::Err: fmt::Debug, { type Output = Self; fn parse(s: &str) -> Self::Output { s.parse().unwrap_or_else(|_| { panic!("Parse error!: ({}: {})", s, any::type_name::<Self>(),) }) } } pub struct Usize1 {} impl Token for Usize1 { type Output = usize; fn parse(s: &str) -> Self::Output { usize::parse(s) .checked_sub(1) .expect("Parse error! (Zero substruction error of Usize1)") } } } mod multi_token { use super::{Token, Tokenizer}; use std::{io::BufRead, iter, marker}; pub trait Parser: Sized { type Output; fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> Self::Output; fn vec(self, len: usize) -> VecLen<Self> { VecLen { len, elem: self } } } pub struct Leaf<T>(pub(super) marker::PhantomData<T>); impl<T: Token> Parser for Leaf<T> { type Output = T::Output; fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> T::Output { server.parse::<T>() } } pub struct VecLen<T> { pub len: usize, pub elem: T, } impl<T: Parser> Parser for VecLen<T> { type Output = Vec<T::Output>; fn parse<S: BufRead>(&self, server: &mut Tokenizer<S>) -> Self::Output { iter::repeat_with(|| self.elem.parse(server)) .take(self.len) .collect() } } pub trait RawTuple { type LeafTuple: Parser; fn leaf_tuple() -> Self::LeafTuple; } pub trait ParserTuple { type Tuple: Parser; fn tuple(self) -> Self::Tuple; } pub struct Tuple<T>(pub T); macro_rules! impl_tuple { ($($t:ident: $T:ident),*) => { impl<$($T),*> Parser for Tuple<($($T,)*)> where $($T: Parser,)* { type Output = ($($T::Output,)*); #[allow(unused_variables)] fn parse<S: BufRead >(&self, server: &mut Tokenizer<S>) -> Self::Output { match self { Tuple(($($t,)*)) => { ($($t.parse(server),)*) } } } } impl<$($T: Token),*> RawTuple for ($($T,)*) { type LeafTuple = Tuple<($(Leaf<$T>,)*)>; fn leaf_tuple() -> Self::LeafTuple { Tuple(($($T::leaf(),)*)) } } impl<$($T: Parser),*> ParserTuple for ($($T,)*) { type Tuple = Tuple<($($T,)*)>; fn tuple(self) -> Self::Tuple { Tuple(self) } } }; } impl_tuple!(); impl_tuple!(t1: T1); impl_tuple!(t1: T1, t2: T2); impl_tuple!(t1: T1, t2: T2, t3: T3); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7); impl_tuple!( t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7, t8: T8 ); } trait Scanner: BufRead + Sized { fn tokenizer(self) -> Tokenizer<Self> { Tokenizer::new(self) } } impl<R: BufRead> Scanner for R {} } pub use self::i::{with_stdin, with_str}; mod prelude { pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1}; } } // }}}