結果

問題 No.475 最終日 - Writerの怠慢
ユーザー hatoohatoo
提出日時 2017-10-19 01:52:42
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 3,889 bytes
コンパイル時間 20,208 ms
コンパイル使用メモリ 379,268 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-29 11:58:52
合計ジャッジ時間 21,731 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 8 ms
5,376 KB
testcase_13 AC 10 ms
5,376 KB
testcase_14 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering, Reverse};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn get<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn get2<T: FromStr, U: FromStr>() -> (T, U)
    where
        <T as FromStr>::Err: Debug,
        <U as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    }

    #[allow(dead_code)]
    pub fn get3<S: FromStr, T: FromStr, U: FromStr>() -> (S, T, U)
    where
        <S as FromStr>::Err: Debug,
        <T as FromStr>::Err: Debug,
        <U as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    }
}

// std::cmp::Reverse doesn't have Clone.
#[derive(Eq, PartialEq, Clone)]
struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

#[allow(unused_macros)]
macro_rules! debug {
    ($x: expr) => {
        println!("{}: {:?}", stringify!($x), $x)
    }
}


struct BIT {
    buf: Vec<usize>,
}

impl BIT {
    fn new(n: usize) -> BIT {
        BIT { buf: vec![0; n + 1] }
    }

    fn sum(&self, i: usize) -> usize {
        let mut i = i;
        let mut s = 0;
        while i > 0 {
            s += self.buf[i];
            i = i & (i - 1);
        }
        s
    }

    fn add(&mut self, i: usize, x: usize) {
        let mut i = i as i64;
        while i < self.buf.len() as i64 {
            self.buf[i as usize] += x;
            i += i & -i;
        }
    }
}

fn score(s: i64, rank: i64) -> i64 {
    let rhs = 50.0 * s as f64 / (0.8 + 0.2 * rank as f64);
    50 * s + rhs as i64
}

fn main() {
    let (n, s, id): (usize, i64, usize) = util::get3();
    let mut a: Vec<i64> = util::gets();

    let mut bit = BIT::new(n);
    let me = a[id] + 100 * s;
    a.remove(id);

    let m = n - 1;
    let scores: Vec<i64> = (1..m + 1).rev().map(|i| score(s, i as i64)).collect();

    let ans = a.iter()
        .map(|&x| {
            let rank = match scores.binary_search(&(me - x + 1)) {
                Ok(i) => Some(i),
                Err(i) => if i == scores.len() { None } else { Some(i) },
            };
            rank.map(|i| if i == 0 {
                0.0
            } else {
                let res = (i - bit.sum(i)) as f64 / m as f64;
                bit.add(i, 1);
                res
            }).unwrap_or(1.0)
        })
        .fold(1.0, |a, b| a * b);

    println!("{}", ans);

}
0