結果
問題 |
No.702 中央値を求めよ LIMITED
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }