結果

問題 No.702 中央値を求めよ LIMITED
コンテスト
ユーザー tnakao0123
提出日時 2018-06-18 20:28:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,169 bytes
コンパイル時間 823 ms
コンパイル使用メモリ 79,764 KB
最終ジャッジ日時 2025-01-01 22:19:13
合計ジャッジ時間 1,615 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:34:9: error: ‘uint32_t’ does not name a type
   34 | typedef uint32_t ui;
      |         ^~~~~~~~
main.cpp:24:1: note: ‘uint32_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
   23 | #include<functional>
  +++ |+#include <cstdint>
   24 | 
main.cpp:39:1: error: ‘ui’ does not name a type; did you mean ‘uint’?
   39 | ui x = 0, y = 1, z = 2, w = 3;
      | ^~
      | uint
main.cpp:43:8: error: ‘ui’ does not name a type; did you mean ‘uint’?
   43 | inline ui generate(ui &x, ui &y, ui &z, ui &w) {
      |        ^~
      |        uint
main.cpp: In function ‘int main()’:
main.cpp:55:3: error: ‘ui’ was not declared in this scope
   55 |   ui seed;
      |   ^~
main.cpp:56:16: error: ‘seed’ was not declared in this scope
   56 |   scanf("%u", &seed);
      |                ^~~~
main.cpp:63:7: error: expected ‘;’ before ‘x’
   63 |     ui x = seed, y = 1, z = 2, w = 3;
      |       ^~
      |       ;
main.cpp:65:9: error: expected ‘;’ before ‘ai’
   65 |       ui ai = generate(x, y, z, w);
      |         ^~~
      |         ;
main.cpp:66:11: error: ‘ai’ was not declared in this scope; did you mean ‘i’?
   66 |       if (ai <= m) cnt++;
      |           ^~
      |           i

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 702.cc: No.702 中央値を求めよ LIMITED - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int N = 10000001;
const int MED = (N + 1) / 2;

/* typedef */

typedef uint32_t ui;
typedef long long ll;

/* global variables */

ui x = 0, y = 1, z = 2, w = 3;

/* subroutines */

inline ui generate(ui &x, ui &y, ui &z, ui &w) {
  ui t = (x ^ (x << 11));
  x = y;
  y = z;
  z = w;
  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  return w;
}

/* main */

int main() {
  ui seed;
  scanf("%u", &seed);

  ll l = -1, r = (1LL << 32) - 1;
  while (l + 1 < r) {
    ll m = (l + r) / 2;

    int cnt = 0;
    ui x = seed, y = 1, z = 2, w = 3;
    for (int i = 0; i < N; i++) {
      ui ai = generate(x, y, z, w);
      if (ai <= m) cnt++;
    }

    if (cnt >= MED) r = m;
    else l = m;
  }

  printf("%lld\n", r);
  return 0;
}
0