結果

問題 No.475 最終日 - Writerの怠慢
コンテスト
ユーザー hatoo
提出日時 2017-10-19 02:10:55
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 3,854 bytes
コンパイル時間 23,177 ms
コンパイル使用メモリ 399,092 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-18 15:03:15
合計ジャッジ時間 15,867 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
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