結果

問題 No.702 中央値を求めよ LIMITED
ユーザー LyricalMaestro
提出日時 2024-09-08 14:16:16
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,640 bytes
コンパイル時間 12,987 ms
コンパイル使用メモリ 395,716 KB
実行使用メモリ 8,740 KB
最終ジャッジ日時 2024-09-08 14:16:50
合計ジャッジ時間 21,036 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1
other -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;


const MAX: u32 = u32::MAX;

struct Generator {
    x: u32,
    y: u32,
    z: u32,
    w: u32,
}

impl Generator {
    fn new(seed: u32) -> Generator {
        Generator {
            x: seed,
            y: 1,
            z: 2,
            w: 3,
        }
    }

    fn generate(&mut self) -> u32 {
        let t = (self.x ^ (self.x << 11)) & MAX;
        self.x = self.y;
        self.y = self.z;
        self.z = self.w;
        self.w = ((self.w ^ (self.w >> 19)) ^ (t ^ (t >> 8))) & MAX;
        self.w
    }
}

fn solve(n: u32, seed: u32, value: u32) -> bool {
    let mut generator = Generator::new(seed);

    let n2 = n / 2;
    let n1 = n2 + 1;

    let mut cnt = 0;
    for _ in 0..n {
        let x = generator.generate();
        if x >= value {
            cnt += 1;
        }
    }
    cnt >= n1
}

fn main() {
    input! {
        seed: u32
    }


    let n: u32 = 10_000_001;

    let mut generator = Generator::new(seed);
    let mut mean = 0 as u128;
    let mut mean2 = 0 as u128;
    for _ in 0..n {
        let g = generator.generate() as u128;
        mean += g;
        mean2 += g * g;
    }
    let m = (mean as f64) / (n as f64);
    let var = ((mean2 as f64) / (n as f64)) - (m * m);
    let stdev = var.sqrt();

    let mut low: u32 = (m - stdev) as u32;
    let mut high: u32 = (m + stdev) as u32;

    while high - low > 1 {
        let mid = (high + low) >> 1;
        if solve(n, seed, mid) {
            low = mid;
        } else {
            high = mid;
        }
    }

    if solve(n, seed, high) {
        println!("{}", high);
    } else {
        println!("{}", low);
    }
}
0