提出 #40898345
ソースコード 拡げる
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;
}
}
提出情報
ジャッジ結果
| セット名 |
Sample |
All |
| 得点 / 配点 |
0 / 0 |
500 / 500 |
| 結果 |
|
|
| セット名 |
テストケース |
| 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 |
| ケース名 |
結果 |
実行時間 |
メモリ |
| 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 |