yukicoder : No.702 中央値を求めよ LIMITED

こういうのをさっくり解けるようになっておきたい。
https://yukicoder.me/problems/no/702

問題

(10^7+1)要素の乱数列のシード値と乱数列の生成アルゴリズムが与えられる。
中央値を求めよ。
ただしメモリは32MBしか利用できない。

解法

当然全要素をメモリに入れてソートなんてできない。
そこで正解値を二分探索しよう。
乱数列を32回ほど辿る必要があるが、なんとか間に合う。

ll N;
uint32_t x = 0, y = 1, z = 2, w = 3;
uint32_t generate() { 
    uint32_t t = (x^(x<<11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
    return w;
}

vector<ll> cand;

void solve() {
	int i,j,k,l,r; string s;
	
	cin>>k;
	N=10000001;
	ll v=0;
	for(i=32;i>=0;i--) {
		x=k;
		y = 1, z = 2, w = 3;
		int num=0;
		FOR(j,N) if(generate()<=v+(1LL<<i)) num++;
		if(num<N/2+1) v+=1LL<<i;
		
	}
	cout<<v+1<<endl;
	
}

まとめ

前回の双子コンのせいか、なんとかメモリ使用量を削減する方に走ってしまった。