#578056 (Rust) No.723 2つの数の和

• 問題: No.723 2つの数の和
• ユーザー: qryxip
• 提出日時: 2020-11-09 19:43:32
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 17 ms / 2,000 ms
• コード長: 8,580 bytes
• コンパイル時間: 8,109 ms
• コンパイル使用メモリ: 158,916 KB
• 実行使用メモリ: 4,360 KB
• 最終ジャッジ日時: 2023-09-29 22:14:13
• 合計ジャッジ時間: 4,572 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,356 KB
testcase_01	AC	1 ms; 4,352 KB
testcase_02	AC	1 ms; 4,356 KB
testcase_03	AC	12 ms; 4,352 KB
testcase_04	AC	17 ms; 4,356 KB
testcase_05	AC	15 ms; 4,356 KB
testcase_06	AC	16 ms; 4,356 KB
testcase_07	AC	7 ms; 4,360 KB
testcase_08	AC	8 ms; 4,356 KB
testcase_09	AC	16 ms; 4,356 KB
testcase_10	AC	7 ms; 4,356 KB
testcase_11	AC	2 ms; 4,356 KB
testcase_12	AC	9 ms; 4,356 KB
testcase_13	AC	17 ms; 4,352 KB
testcase_14	AC	5 ms; 4,356 KB
testcase_15	AC	7 ms; 4,352 KB
testcase_16	AC	10 ms; 4,356 KB
testcase_17	AC	13 ms; 4,352 KB
testcase_18	AC	8 ms; 4,352 KB
testcase_19	AC	9 ms; 4,356 KB
testcase_20	AC	1 ms; 4,352 KB
testcase_21	AC	1 ms; 4,356 KB
testcase_22	AC	1 ms; 4,356 KB
testcase_23	AC	14 ms; 4,356 KB
testcase_24	AC	5 ms; 4,352 KB

ソースコード

//! # Bundled libraries
//!
//! ## `input` (private)
//!
//! Expanded to `crate::input`.
//!
//! ## `partition_point` (private)
//!
//! Expanded to `crate::partition_point`.

// verify-helper: PROBLEM https://yukicoder.me/problems/no/723

/*#[macro_use]
extern crate input as _;*/

use partition_point::RangeBoundsExt as _;

fn main() {
    input! {
        n: usize,
        x: u32,
        mut r#as: [u32; n],
    }

    r#as.sort();

    let ans = (0..n)
        .map(|i| {
            let s = (i..n).partition_point(|j| r#as[i] + r#as[j] <= x);
            let t = (i..n).partition_point(|j| r#as[i] + r#as[j] < x);
            2 * (s - t) - usize::from(2 * r#as[i] == x)
        })
        .sum::<usize>();
    println!("{}", ans);
}

// The following code was expanded by `cargo-equip`.

#[allow(dead_code)]
mod input {
    pub use crate::{input, input_inner, read, readable};
    use std::{
        cell::RefCell,
        fmt::Debug,
        io::{self, BufRead, Read},
        rc::Rc,
        str::{FromStr, SplitWhitespace},
    };

    #[macro_export]
    macro_rules! input {
        (from $scanner:ident; $($tt:tt)*) => {
            $crate::input::input_inner!(@scanner($scanner), @tts($($tt)*))
        };
        ($($tt:tt)*) => {
            let __scanner = $crate::input::DEFAULT_SCANNER.with(|__scanner| __scanner.clone());
            let mut __scanner_ref = __scanner.borrow_mut();
            if let $crate::input::Scanner::Uninited = *__scanner_ref {
                *__scanner_ref = $crate::input::Scanner::stdin_auto().unwrap();
            }
            $crate::input::input_inner!(@scanner(__scanner_ref), @tts($($tt)*));
            ::std::mem::drop(__scanner_ref);
            ::std::mem::drop(__scanner);
        };
    }

    #[macro_export]
    macro_rules! input_inner {
        (@scanner($scanner:ident), @tts()) => {};
        (@scanner($scanner:ident), @tts(mut $single_tt_pat:tt : $readable:tt)) => {
            let mut $single_tt_pat = $crate::input::read!(from $scanner { $readable });
        };
        (@scanner($scanner:ident), @tts($single_tt_pat:tt : $readable:tt)) => {
            let $single_tt_pat = $crate::input::read!(from $scanner { $readable });
        };
        (@scanner($scanner:ident), @tts(mut $single_tt_pat:tt : $readable:tt, $($rest:tt)*)) => {
            $crate::input::input_inner!(@scanner($scanner), @tts(mut $single_tt_pat: $readable));
            $crate::input::input_inner!(@scanner($scanner), @tts($($rest)*));
        };
        (@scanner($scanner:ident), @tts($single_tt_pat:tt : $readable:tt, $($rest:tt)*)) => {
            $crate::input::input_inner!(@scanner($scanner), @tts($single_tt_pat: $readable));
            $crate::input::input_inner!(@scanner($scanner), @tts($($rest)*));
        };
    }

    #[macro_export]
    macro_rules! read {
        (from $scanner:ident { [$tt:tt] }) => {
            $crate::input::read!(from $scanner { [$tt; $crate::read!(from $scanner { usize })] })
        };
        (from $scanner:ident  { [$tt:tt; $n:expr] }) => {
            (0..$n).map(|_| $crate::input::read!(from $scanner { $tt })).collect::<Vec<_>>()
        };
        (from $scanner:ident { ($($tt:tt),+) }) => {
            ($($crate::read!(from $scanner { $tt })),*)
        };
        (from $scanner:ident { $ty:ty }) => {
            <$ty as $crate::input::Readable>::read_from_scanner(&mut $scanner)
        };
    }

    #[macro_export]
    macro_rules! readable {
        ($name:ident; |$scanner:ident| { $($body:tt)* }) => {
            $crate::input::readable!($name; |$scanner| -> () { $($body)* });
        };
        ($name:ident; |$scanner:ident| $expr:expr) => {
            $crate::input::readable!($name; |$scanner| -> () { $expr });
        };
        ($name:ident; |$scanner:ident| -> $output:ty { $($body:tt)* }) => {
            enum $name {}

            impl $crate::input::Readable for $name {
                type Output = $output;

                fn read_from_scanner(mut $scanner: &mut $crate::input::Scanner) -> $output {
                    $($body)*
                }
            }
        };
    }

    pub enum Scanner {
        Uninited,
        Once {
            words: SplitWhitespace<'static>,
        },
        Lines {
            rdr: Box<dyn BufRead>,
            words: SplitWhitespace<'static>,
        },
    }

    impl Scanner {
        pub fn stdin_auto() -> io::Result<Self> {
            if cfg!(debug_assertions) {
                Ok(Self::lines(Box::leak(Box::new(io::stdin())).lock()))
            } else {
                Self::once(io::stdin())
            }
        }

        pub fn once<R: Read>(mut rdr: R) -> io::Result<Self> {
            let mut buf = String::with_capacity(1024);
            rdr.read_to_string(&mut buf)?;
            let words = Box::leak(buf.into_boxed_str()).split_whitespace();
            Ok(Self::Once { words })
        }

        pub fn lines<R: BufRead + 'static>(rdr: R) -> Self {
            Self::Lines {
                rdr: Box::new(rdr),
                words: "".split_whitespace(),
            }
        }

        pub fn parse_next_unwrap<T: FromStr>(&mut self) -> T
        where
            T::Err: Debug,
        {
            match self {
                Self::Uninited => None,
                Self::Once { words } => words.next(),
                Self::Lines { rdr, words } => words.next().or_else(|| {
                    let mut line = "".to_owned();
                    rdr.read_line(&mut line).unwrap();
                    *words = Box::leak(line.into_boxed_str()).split_whitespace();
                    words.next()
                }),
            }
            .expect("reached EOF")
            .parse()
            .unwrap()
        }
    }

    thread_local! {
        pub static DEFAULT_SCANNER: Rc<RefCell<Scanner>> = Rc::new(RefCell::new(Scanner::Uninited));
    }

    pub trait Readable {
        type Output;

        fn read_from_scanner(scanner: &mut Scanner) -> Self::Output;
    }

    impl<T: FromStr> Readable for T
    where
        T::Err: Debug,
    {
        type Output = Self;

        fn read_from_scanner(scanner: &mut Scanner) -> Self {
            scanner.parse_next_unwrap()
        }
    }
}

#[allow(dead_code)]
mod partition_point {
    use std::{
        fmt,
        ops::{Add, Bound, Div, RangeBounds, Sub},
    };

    pub trait RangeBoundsExt<T: PrimitiveInteger>: RangeBounds<T> {
        fn partition_point<P>(&self, mut pred: P) -> T
        where
            P: FnMut(T) -> bool,
        {
            let mut start = match self.start_bound() {
                Bound::Included(&x) => x,
                Bound::Excluded(&x) if x > T::MIN_VALUE => x - T::ONE,
                _ => T::MIN_VALUE,
            };

            let mut end = match self.end_bound() {
                Bound::Included(&x) if x < T::MAX_VALUE => x + T::ONE,
                Bound::Excluded(&x) => x,
                _ if pred(T::MAX_VALUE) => {
                    panic!("the predicate is satisfied at {:?}", T::MAX_VALUE)
                }
                _ => T::MAX_VALUE,
            };

            while start != end {
                let mid = start + (end - start) / (T::ONE + T::ONE);
                if pred(mid) {
                    start = mid + T::ONE;
                } else {
                    end = mid;
                }
            }
            start
        }
    }

    impl<T: PrimitiveInteger, R: RangeBounds<T>> RangeBoundsExt<T> for R {}

    pub trait SliceExt {
        type Item;

        fn partition_point<P>(&self, pred: P) -> usize
        where
            P: FnMut(&Self::Item) -> bool;
    }

    impl<T> SliceExt for [T] {
        type Item = T;

        fn partition_point<P>(&self, mut pred: P) -> usize
        where
            P: FnMut(&T) -> bool,
        {
            (0..self.len()).partition_point(|i| pred(&self[i]))
        }
    }

    pub trait PrimitiveInteger:
        Copy + Ord + Add<Output = Self> + Sub<Output = Self> + Div<Output = Self> + fmt::Debug
    {
        const ZERO: Self;
        const ONE: Self;
        const MIN_VALUE: Self;
        const MAX_VALUE: Self;
    }

    macro_rules! impl_primitive_integer(($($ty:ty),*) => {
        $(
            impl PrimitiveInteger for $ty {
                const ZERO: Self = 0;
                const ONE: Self = 1;
                const MIN_VALUE: Self = <$ty>::min_value();
                const MAX_VALUE: Self = <$ty>::max_value();
            }
        )*
    });

    impl_primitive_integer!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
}