#727758 (Rust) No.919 You Are A Project Manager

提出ソース

結果

問題	No.919 You Are A Project Manager
ユーザー	ngtkana
提出日時	2022-01-02 10:22:23
言語	Rust (1.77.0)
結果	AC
実行時間	227 ms / 3,000 ms
コード長	27,853 bytes
コンパイル時間	1,826 ms
コンパイル使用メモリ	195,184 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-19 15:49:30
合計ジャッジ時間	8,746 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	176 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	33 ms 5,376 KB
testcase_05	AC	36 ms 5,376 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	86 ms 5,376 KB
testcase_08	AC	18 ms 5,376 KB
testcase_09	AC	14 ms 5,376 KB
testcase_10	AC	26 ms 5,376 KB
testcase_11	AC	25 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	31 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	10 ms 5,376 KB
testcase_16	AC	48 ms 5,376 KB
testcase_17	AC	173 ms 5,376 KB
testcase_18	AC	179 ms 5,376 KB
testcase_19	AC	184 ms 5,376 KB
testcase_20	AC	202 ms 5,376 KB
testcase_21	AC	181 ms 5,376 KB
testcase_22	AC	94 ms 5,376 KB
testcase_23	AC	91 ms 5,376 KB
testcase_24	AC	96 ms 5,376 KB
testcase_25	AC	93 ms 5,376 KB
testcase_26	AC	206 ms 5,376 KB
testcase_27	AC	184 ms 5,376 KB
testcase_28	AC	216 ms 5,376 KB
testcase_29	AC	173 ms 5,376 KB
testcase_30	AC	172 ms 5,376 KB
testcase_31	AC	165 ms 5,376 KB
testcase_32	AC	167 ms 5,376 KB
testcase_33	AC	102 ms 5,376 KB
testcase_34	AC	105 ms 5,376 KB
testcase_35	AC	225 ms 5,376 KB
testcase_36	AC	224 ms 5,376 KB
testcase_37	AC	221 ms 5,376 KB
testcase_38	AC	227 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB
testcase_40	AC	9 ms 5,376 KB
testcase_41	AC	3 ms 5,376 KB
testcase_42	AC	4 ms 5,376 KB
testcase_43	AC	6 ms 5,376 KB
testcase_44	AC	14 ms 5,376 KB
testcase_45	AC	4 ms 5,376 KB
testcase_46	AC	13 ms 5,376 KB
testcase_47	AC	94 ms 5,376 KB
testcase_48	AC	90 ms 5,376 KB
testcase_49	AC	98 ms 5,376 KB
testcase_50	AC	91 ms 5,376 KB
testcase_51	AC	83 ms 5,376 KB
testcase_52	AC	64 ms 5,376 KB
testcase_53	AC	85 ms 5,376 KB
testcase_54	AC	10 ms 5,376 KB
testcase_55	AC	0 ms 5,376 KB
testcase_56	AC	1 ms 5,376 KB
testcase_57	AC	1 ms 5,376 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused imports: `Leaf`, `Tuple`, `VecLen`
   --> 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`
   --> main.rs:804:35
    |
804 |     pub use self::i::{with_stdin, with_str};
    |                                   ^^^^^^^^

warning: unused imports: `ParserTuple`, `Parser`, `RawTuple`, `Token`, `Usize1`
   --> main.rs:806:28
    |
806 |         pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1};
    |                            ^^^^^^  ^^^^^^^^^^^  ^^^^^^^^  ^^^^^  ^^^^^^

warning: 3 warnings emitted

ソースコード

raw source code

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(&current.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};
    }
}
// }}}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード