結果

問題 No.475 最終日 - Writerの怠慢
ユーザー hatoohatoo
提出日時 2017-10-19 02:10:55
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 3,854 bytes
コンパイル時間 14,035 ms
コンパイル使用メモリ 380,228 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-29 11:59:15
合計ジャッジ時間 15,464 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 15 ms
5,376 KB
testcase_07 AC 16 ms
5,376 KB
testcase_08 AC 16 ms
5,376 KB
testcase_09 AC 16 ms
5,376 KB
testcase_10 AC 16 ms
5,376 KB
testcase_11 AC 16 ms
5,376 KB
testcase_12 AC 9 ms
5,376 KB
testcase_13 AC 14 ms
5,376 KB
testcase_14 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: struct `BIT` is never constructed
  --> src/main.rs:97:8
   |
97 | struct BIT {
   |        ^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: associated items `new`, `sum`, and `add` are never used
   --> src/main.rs:102:8
    |
101 | impl BIT {
    | -------- associated items in this implementation
102 |     fn new(n: usize) -> BIT {
    |        ^^^
...
106 |     fn sum(&self, i: usize) -> usize {
    |        ^^^
...
116 |     fn add(&mut self, i: usize, x: usize) {
    |        ^^^

ソースコード

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 me = a[id] + 100 * s;
    a.remove(id);
    a.sort_by_key(|&x| Reverse(x));

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

    let ans = a.iter()
        .enumerate()
        .map(|(k, &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 k > i {
                0.0
            } else {
                (i - k) as f64 / (m - k) as f64
            }).unwrap_or(1.0)
        })
        .fold(1.0, |a, b| a * b);

    println!("{}", ans);

}
0