結果

問題 No.702 中央値を求めよ LIMITED
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-09-08 14:16:16
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 496 ms
6,816 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

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