結果

問題 No.702 中央値を求めよ LIMITED
コンテスト
ユーザー obakyan
提出日時 2019-04-29 17:23:14
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,155 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 869 ms
コンパイル使用メモリ 80,092 KB
最終ジャッジ日時 2026-05-16 21:09:27
合計ジャッジ時間 3,697 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:13:1: error: 'uint32_t' does not name a type
   13 | uint32_t x = 0, y = 1, z = 2, w = 3;
      | ^~~~~~~~
main.cpp:10:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    9 | #include <iomanip>
  +++ |+#include <cstdint>
   10 | #define L64 long long
main.cpp:15:1: error: 'uint32_t' does not name a type
   15 | uint32_t generate() {
      | ^~~~~~~~
main.cpp:15:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:24:11: error: 'uint32_t' was not declared in this scope
   24 | int check(uint32_t a, bool& same){
      |           ^~~~~~~~
main.cpp:24:11: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:24:23: error: expected primary-expression before 'bool'
   24 | int check(uint32_t a, bool& same){
      |                       ^~~~
main.cpp:24:33: error: expression list treated as compound expression in initializer [-fpermissive]
   24 | int check(uint32_t a, bool& same){
      |                                 ^
main.cpp: In function 'int main()':
main.cpp:45:3: error: 'uint32_t' was not declared in this scope
   45 |   uint32_t min, max;
      |   ^~~~~~~~
main.cpp:45:3: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
main.cpp:46:3: error: 'min' was not declared in this scope; did you mean 'std::min'?
   46 |   min = 0; max = 4294967295;
      |   ^~~
      |   std::min
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/algorithm:63,
                 from main.cpp:5:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_algo.h:5774:5: note: 'std::min' declared here
 5774 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
main.cpp:46:12: error: 'max' was not declared in this scope; did you mean 'std::max'?
   46 |   min = 0; max = 42949672

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstdlib>
#include <cstddef>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#define L64 long long
#define MOD (1000000007LL)

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

int check(uint32_t a, bool& same){
  same = false;
  uint32_t q;
  int ret = 0;
  x = g_seed;
  y = 1;
  z = 2;
  w = 3;
  for (int i = 0; i < 10000001; i++){
    q = generate();
    if(q < a){
      ret++;
    } else if(q == a){ same = true; }
  }
  return ret;
}

int main(void)
{
  bool same = false;
  std::cin >> g_seed;
  uint32_t min, max;
  min = 0; max = 4294967295;
  while(min != max){
    uint32_t mid = (uint32_t)((((uint64_t)min + (uint64_t)max) / (uint64_t)2));
    int lownum = check(mid, same);
    if(lownum < 5000000){
      min = mid + 1;
    } else if(lownum == 5000000){
      if(same){
        std::cout << mid << std::endl;
        break;
      } else {
        min = mid + 1;
      }
    } else {
      max = mid;
    }
  }
}
0