結果

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

ソースコード

diff # 

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() {
    use std::io;

    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("Failed to read input");
    let seed: u32 = input.trim().parse().expect("Input is not a valid u32");

    let n: u32 = 10_000_001;

    let mut low: u32 = 0;
    let mut high: u32 = 0;
    for i in 0..32 {
        high += 1 << i;
    }

    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