結果
問題 | No.702 中央値を求めよ LIMITED |
ユーザー |
|
提出日時 | 2018-09-03 16:28:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,766 ms / 5,000 ms |
コード長 | 798 bytes |
コンパイル時間 | 2,194 ms |
コンパイル使用メモリ | 193,084 KB |
最終ジャッジ日時 | 2025-01-06 12:48:21 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> int main() { uint32_t seed; uint64_t inf = 0U, sup = ~0U; std::cin >> seed; constexpr uint32_t HALF = 5000001, ALL = 2 * HALF - 1; auto ok = [&](const uint64_t m) { uint32_t x = seed, y = 1, z = 2, w = 3, l = 0, e = 0, u = 0; auto gen = [&]() { const uint32_t t = (x ^ (x << 11)); return x=y,y=z,z=w,w=(w^(w>>19))^(t^(t>>8)); }; for (uint32_t i = 0, v; i < ALL; i++) { v = gen(), (v < m ? l : v == m ? e : u)++; if (l >= HALF) { return 1; } if (u >= HALF) { return -1; } } return 0; }; while (true) { const uint64_t mid = (sup + inf) / 2; if (ok(mid) == 0) { return std::cout << mid << std::endl, 0; } (ok(mid) == -1 ? inf : sup) = mid; } }