Submission #40898345 - AtCoder Beginner Contest 236

Contest Duration: 2022-01-23 21:00:00+0900 - 2022-01-23 22:40:00+0900 (local time) (100 minutes) Back to Home

Submission #40898345

Source Code Expand

use proconio::input;

use nekolib::{math::FractionBisect, traits::Bisect};

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

    println!("{}", average(&a));
    println!("{}", median(&a));
}

fn average(a: &[i64]) -> f64 {
    // (Sum (ai)) / k >= p / q
    // (Sum (ai - p / q)) >= 0
    // Sum(q ai - p) >= 0
    let n = a.len();

    let oo = 2 * 10_i64.pow(18);
    let (_, hi) = (n as i64).fraction_bisect(|p, q| {
        let mut dp = vec![vec![-oo; n + 1]; 2];
        dp[0][0] = 0;
        for i in 0..n {
            for j in 0..2 {
                if dp[j][i] == -oo {
                    continue;
                }
                let cur = dp[j][i];
                let ncur = dp[j][i] + (q * a[i] - p);
                {
                    dp[0][i + 1] = dp[0][i + 1].max(ncur);
                }
                if j == 0 {
                    dp[1][i + 1] = dp[1][i + 1].max(cur);
                }
            }
        }
        dp[0][n].max(dp[1][n]) > 0
    });

    hi.0 as f64 / hi.1 as f64
}

fn median(a: &[i64]) -> i64 {
    let n = a.len();
    let oo = 2 * 10_i64.pow(15);

    // x 以下の値が ceil(n/2)-1 個以上あればよい。
    // [S S x L L], [S S x L L L]
    // #{y | y <= x} - #{y | y > x} <= 1 ならばよい。
    // x 以下の値を 1、x より大きい値を -1 として数える。

    let med = |mid| {
        let mut dp = vec![vec![oo; n + 1]; 2];
        dp[0][0] = 0;
        for i in 0..n {
            for j in 0..2 {
                let cur = dp[j][i];
                let ncur = dp[j][i] + if a[i] <= mid { 1 } else { -1 };
                {
                    dp[0][i + 1] = dp[0][i + 1].min(ncur);
                }
                if j == 0 {
                    dp[1][i + 1] = dp[1][i + 1].min(cur);
                }
            }
        }
        dp[0][n].min(dp[1][n])
    };

    (0_i64..).bisect(|&mid| med(mid) < 0)
}

/// This module is bundled automatically.
/// See <https://rsk0315.github.io/library-rs/nekolib/> for documentation.
pub mod nekolib {
    pub mod math {
        pub mod fraction_bisect {
            use std::ops::{Add, AddAssign, Mul, Neg};
            pub trait FractionBisect: Sized + SbInt {
                fn fraction_bisect(
                    self,
                    pred: impl Fn(Self, Self) -> bool,
                ) -> ((Self, Self), (Self, Self)) {
                    let bound = self;
                    let fr_neg_infty = (Self::ONE.neg(), Self::ZERO);
                    let fr_zero = (Self::ZERO, Self::ONE);
                    let ztf = pred(fr_zero.0, fr_zero.1);
                    let pred = {
                        if !ztf && !Self::SIGNED {
                            return (fr_zero, fr_zero);
                        }
                        if Self::SIGNED
                            && !ztf
                            && !pred(fr_neg_infty.0, fr_neg_infty.1)
                        {
                            return (fr_neg_infty, fr_neg_infty);
                        }
                        move |fr: Fraction<Self>| {
                            if ztf {
                                pred(fr.0, fr.1)
                            } else {
                                !pred(fr.0.neg(), fr.1)
                            }
                        }
                    };
                    let mut lower = Fraction::zero();
                    let mut upper = Fraction::infty();
                    let (small, large) = 'outer: loop {
                        let cur = lower + upper;
                        if cur.is_deeper(bound) {
                            break (lower, upper);
                        }
                        let tf = pred(cur);
                        let (from, to) =
                            if tf { (lower, upper) } else { (upper, lower) };
                        let mut lo = Self::ONE;
                        let mut hi = lo + Self::ONE;
                        while pred(from + to * hi) == tf {
                            lo += lo;
                            hi += hi;
                            if (from + to * lo).is_deeper(bound) {
                                let steps = bound
                                    .steps(from.into_inner(), to.into_inner());
                                let front = from + to * steps;
                                let res = if tf {
                                    (front, upper)
                                } else {
                                    (lower, front)
                                };
                                break 'outer res;
                            }
                        }
                        while lo.lt1(hi) {
                            let mid = lo.avg(hi);
                            let cur = pred(from + to * mid) == tf;
                            *(if cur { &mut lo } else { &mut hi }) = mid;
                        }
                        let next = from + to * lo;
                        *(if tf { &mut lower } else { &mut upper }) = next;
                    };
                    let (left, right) =
                        if ztf { (small, large) } else { (-large, -small) };
                    (left.into_inner(), right.into_inner())
                }
            }
            impl<I: SbInt> FractionBisect for I {}
            #[derive(Clone, Copy, Eq, PartialEq)]
            struct Fraction<I>(I, I);
            pub trait SbInt:
                Copy
                + Eq
                + PartialOrd<Self>
                + AddAssign<Self>
                + Add<Self, Output = Self>
                + Mul<Self, Output = Self>
                + std::fmt::Display
            {
                const ZERO: Self;
                const ONE: Self;
                const SIGNED: bool;
                fn lt1(self, other: Self) -> bool;
                fn avg(self, other: Self) -> Self;
                fn abs(self) -> Self;
                fn neg(self) -> Self;
                fn steps(self, from: (Self, Self), to: (Self, Self)) -> Self;
            }
            impl<I: SbInt> Neg for Fraction<I> {
                type Output = Self;
                fn neg(self) -> Self { self.neg() }
            }
            macro_rules ! impl_uint { ($ ($ ty : ty) *) => { $ (impl SbInt for $ ty { const ZERO : $ ty = 0 ; const ONE : $ ty = 1 ; const SIGNED : bool = false ; fn lt1 (self , other : Self) -> bool { self + 1 < other } fn avg (self , other : Self) -> Self { self + (other - self) / 2 } fn abs (self) -> Self { self } fn neg (self) -> Self { self . wrapping_neg () } fn steps (self , from : (Self , Self) , to : (Self , Self)) -> Self { if to . 0 == 0 { (self - from . 1) / to . 1 } else if to . 1 == 0 { (self - from . 0) / to . 0 } else { ((self - from . 0) / to . 0) . min ((self - from . 1) / to . 1) } } }) * } }
            impl_uint! { u8 u16 u32 u64 u128 usize }
            macro_rules ! impl_int { ($ ($ ty : ty) *) => { $ (impl SbInt for $ ty { const ZERO : $ ty = 0 ; const ONE : $ ty = 1 ; const SIGNED : bool = true ; fn lt1 (self , other : Self) -> bool { self + 1 < other } fn avg (self , other : Self) -> Self { self + (other - self) / 2 } fn abs (self) -> Self { self . abs () } fn neg (self) -> Self { - self } fn steps (self , from : (Self , Self) , to : (Self , Self)) -> Self { if to . 0 == 0 { (self - from . 1) / to . 1 } else if to . 1 == 0 { (self - from . 0) / to . 0 } else { ((self - from . 0) / to . 0) . min ((self - from . 1) / to . 1) } } }) * } }
            impl_int! { i8 i16 i32 i64 i128 isize }
            impl<I: SbInt> Fraction<I> {
                fn zero() -> Self { Self(I::ZERO, I::ONE) }
                fn infty() -> Self { Self(I::ONE, I::ZERO) }
            }
            impl<I: SbInt> Mul<I> for Fraction<I> {
                type Output = Self;
                fn mul(self, a: I) -> Self { Self(self.0 * a, self.1 * a) }
            }
            impl<I: SbInt> Add<Fraction<I>> for Fraction<I> {
                type Output = Self;
                fn add(self, other: Self) -> Self {
                    Self(self.0 + other.0, self.1 + other.1)
                }
            }
            impl<I: SbInt> Fraction<I> {
                fn is_deeper(self, bound: I) -> bool { self.1.abs() > bound }
                fn neg(self) -> Self { Self(self.0.neg(), self.1) }
                fn into_inner(self) -> (I, I) { (self.0, self.1) }
            }
        }
        pub use self::fraction_bisect::FractionBisect;
    }
    pub mod traits {
        pub mod bisect {
            use std::ops::{Range, RangeFrom, RangeTo};
            pub trait Bisect {
                type Input;
                type Output;
                fn bisect(
                    &self,
                    pred: impl FnMut(&Self::Input) -> bool,
                ) -> Self::Output;
            }
            macro_rules ! impl_bisect_int { ($ t : ty) => { impl Bisect for Range <$ t > { type Input = $ t ; type Output = $ t ; fn bisect (& self , mut pred : impl FnMut (&$ t) -> bool) -> $ t { let Range { start : mut ok , end : mut bad } = * self ; if ! pred (& ok) { return ok ; } while bad - ok > 1 { let mid = ok + (bad - ok) / 2 ; * (if pred (& mid) { & mut ok } else { & mut bad }) = mid ; } bad } } impl Bisect for RangeFrom <$ t > { type Input = $ t ; type Output = $ t ; fn bisect (& self , mut pred : impl FnMut (&$ t) -> bool) -> $ t { let RangeFrom { start : ok } = * self ; if ! pred (& ok) { return ok ; } let mut w = 1 ; while pred (& (ok + w)) { w *= 2 ; } (ok .. ok + w) . bisect (pred) } } impl Bisect for RangeTo <$ t > { type Input = $ t ; type Output = $ t ; fn bisect (& self , mut pred : impl FnMut (&$ t) -> bool) -> $ t { let RangeTo { end : bad } = * self ; if pred (& bad) { return bad ; } let mut w = 1 ; while ! pred (& (bad - w)) { w *= 2 ; } (bad - w .. bad) . bisect (pred) } } } ; ($ ($ t : ty) *) => { $ (impl_bisect_int ! { $ t }) * } ; }
            impl_bisect_int! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }
            macro_rules ! impl_bisect_float { ($ (($ fty : ty , $ ity : ty , $ uty : ty , $ w : literal , $ f2u : ident , $ u2f : ident , $ mask : ident) ,) *) => { $ (impl Bisect for Range <$ fty > { type Input = $ fty ; type Output = $ fty ; fn bisect (& self , mut pred : impl FnMut (&$ fty) -> bool) -> $ fty { let Range { start , end } = * self ; let start = $ f2u (start) ; let end = $ f2u (end) ; $ u2f ((start .. end) . bisect (|& u | pred (&$ u2f (u)))) } } fn $ mask (u : $ uty) -> $ uty { ((u as $ ity >> ($ w - 1)) as $ uty >> 1) | 1 << ($ w - 1) } fn $ f2u (f : $ fty) -> $ uty { let u = f . to_bits () ; u ^ $ mask (u) } fn $ u2f (u : $ uty) -> $ fty { <$ fty >:: from_bits (u ^ $ mask (! u)) }) * } ; }
            impl_bisect_float! { (f32 , i32 , u32 , 32 , f2u32 , u2f32 , mask32) , (f64 , i64 , u64 , 64 , f2u64 , u2f64 , mask64) , }
            impl<T> Bisect for [T] {
                type Input = T;
                type Output = usize;
                fn bisect(&self, mut pred: impl FnMut(&T) -> bool) -> usize {
                    if self.is_empty() || !pred(&self[0]) {
                        return 0;
                    }
                    let mut ok = 0;
                    let mut bad = self.len();
                    while bad - ok > 1 {
                        let mid = ok + (bad - ok) / 2;
                        *(if pred(&self[mid]) { &mut ok } else { &mut bad }) =
                            mid;
                    }
                    bad
                }
            }
        }
        pub use self::bisect::Bisect;
    }
}

Submission Info

Submission Time	2023-04-23 17:58:36+0900
Task	E - Average and Median
User	rsk0315
Language	Rust (1.42.0)
Score	500
Code Size	11835 Byte
Status	AC
Exec Time	190 ms
Memory	5380 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

500 / 500

Status

× 2

× 33

Set Name	Test Cases
Sample	example_00.txt, example_01.txt
All	example_00.txt, example_01.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt

Case Name	Status	Exec Time	Memory
example_00.txt	AC	6 ms	1988 KiB
example_01.txt	AC	2 ms	2140 KiB
test_00.txt	AC	190 ms	5304 KiB
test_01.txt	AC	184 ms	5252 KiB
test_02.txt	AC	120 ms	4020 KiB
test_03.txt	AC	142 ms	4404 KiB
test_04.txt	AC	149 ms	4788 KiB
test_05.txt	AC	67 ms	3268 KiB
test_06.txt	AC	66 ms	3240 KiB
test_07.txt	AC	82 ms	3436 KiB
test_08.txt	AC	176 ms	5104 KiB
test_09.txt	AC	118 ms	4124 KiB
test_10.txt	AC	189 ms	5176 KiB
test_11.txt	AC	188 ms	5316 KiB
test_12.txt	AC	155 ms	4904 KiB
test_13.txt	AC	139 ms	4636 KiB
test_14.txt	AC	160 ms	4728 KiB
test_15.txt	AC	185 ms	5204 KiB
test_16.txt	AC	184 ms	5316 KiB
test_17.txt	AC	118 ms	4056 KiB
test_18.txt	AC	101 ms	3544 KiB
test_19.txt	AC	167 ms	4760 KiB
test_20.txt	AC	98 ms	4576 KiB
test_21.txt	AC	92 ms	4496 KiB
test_22.txt	AC	45 ms	3412 KiB
test_23.txt	AC	10 ms	2336 KiB
test_24.txt	AC	18 ms	2376 KiB
test_25.txt	AC	74 ms	4452 KiB
test_26.txt	AC	76 ms	4404 KiB
test_27.txt	AC	4 ms	2148 KiB
test_28.txt	AC	60 ms	4488 KiB
test_29.txt	AC	164 ms	5380 KiB
test_30.txt	AC	41 ms	4484 KiB