結果

問題 No.702 中央値を求めよ LIMITED
コンテスト
ユーザー ooaiu
提出日時 2025-07-05 22:16:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 734 ms / 5,000 ms
コード長 660 bytes
コンパイル時間 3,892 ms
コンパイル使用メモリ 272,748 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-07-05 22:17:10
合計ジャッジ時間 23,995 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
const int N = 1e7+1;
u32 x = 0, y = 1, z = 2, w = 3;
u32 generate() {
    u32 t = (x^(x<<11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return w;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	u64 seed;
	cin >> seed;
	u32 lo = 0, hi = -1;
	while(hi - lo > 1) {
		u32 mi = lo + (hi - lo) / 2;
		int t = 0;
		x = seed, y = 1, z = 2, w = 3;
		for(int i = 0; i < N; i++) {
			u32 s = generate();
			if(s < mi) {
				t += 1;
			}
		}
		if(t < N/2 + 1) lo = mi;
		else hi = mi;
	}
	cout << lo << endl;
}
0