中央値を求めよ LIMITED [yukicoder No.702] - はまやんはまやんはまやん

前提知識

二分探索

考察

1. 数列aを全て乗せるのは不可能
2. （どう見ても解けないような問題は、個人的に二分探索を考えるようにしている）
3. できる

解説

二分探索を利用して解こう。
　
「count(c) := c以下である要素数」を作成する。
これを利用すると、全部で10000001要素あって、求めたい中央値をansとすると、
count(ans) = 5000001
count(ans-1) = 5000000
x＜ansならばcount(x)＜5000001
ans≦xならば5000001≦count(x)
という境界条件が現れる。
よって、二分探索をして、境界を求めていこう。

ll seed;
//---------------------------------------------------------------------------------------------------
uint32_t x = 0, y = 1, z = 2, w = 3;
ll generate() {
    uint32_t t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return (ll)w;
}
//---------------------------------------------------------------------------------------------------
int count(ll c) {
    x = seed, y = 1, z = 2, w = 3;
    int res = 0;
    rep(i, 0, 10000001) if (generate() <= c) res++;
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> seed;

    ll ng = 0, ok = infl;
    while (ng + 1 != ok) {
        ll md = (ng + ok) / 2;
        if (5000001 <= count(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}