Submission #56338171

---

Source Code Expand

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: u64,
        a: [u64; n],
    }

    let oo = 10_u64.pow(15);
    let res = (0_u64..oo)
        .bisect(|&x| a.iter().map(|&ai| ai.min(x)).sum::<u64>() <= m);
    if res < oo {
        println!("{}", res - 1);
    } else {
        println!("infinite");
    }
}

trait Bisect {
    type Item;
    fn bisect(&self, f: impl FnMut(&Self::Item) -> bool) -> Self::Item;
}

impl Bisect for std::ops::Range<u64> {
    type Item = u64;
    fn bisect(&self, mut pred: impl FnMut(&Self::Item) -> bool) -> Self::Item {
        let std::ops::Range { start, end } = *self;
        assert!(start <= end, "range must be valid.");
        if !pred(&start) {
            return start;
        }

        let mut ok = start;
        let mut bad = end;
        while let Some(mid) = ok.checked_midpoint(&bad) {
            *(if pred(&mid) { &mut ok } else { &mut bad }) = mid;
        }
        bad
    }
}

trait BisectTy: Sized {
    fn checked_midpoint(&self, other: &Self) -> Option<Self>;
}

macro_rules! impl_uint {
    ( $($ty:ty)* ) => { $(
        impl BisectTy for $ty {
            fn checked_midpoint(&self, &other: &Self) -> Option<Self> {
                (other - self > 1).then(|| self + (other - self) / 2)
            }
        }
    )* };
}

impl_uint! { u8 u16 u32 u64 u128 usize }

Submission Info

Judge Result