結果
問題 | No.702 中央値を求めよ LIMITED |
ユーザー |
|
提出日時 | 2018-06-15 23:08:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,371 bytes |
コンパイル時間 | 868 ms |
コンパイル使用メモリ | 102,316 KB |
実行使用メモリ | 19,768 KB |
最終ジャッジ日時 | 2024-11-14 20:27:55 |
合計ジャッジ時間 | 2,960 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 WA * 2 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <array>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>using namespace std;class Xorshift{private:uint32_t x, y, z, w;public:Xorshift(uint32_t seed){x = seed;y = 1;z = 2;w = 3;}uint32_t operator()(){uint32_t t=(x^(x<<11));x=y; y=z; z=w;return w=(w^(w>>19))^(t^(t>>8));}};const unsigned MID = 0x80000000;const int LEN = 0x200000;int main(){int seed;cin >> seed;Xorshift xorshift(seed);int n = 10000001;vector<int> cnt(LEN*2+1);for(int i=0; i<n; ++i){long long a = xorshift();a -= MID;if(a < -LEN)a = -LEN;else if(a > LEN)a = LEN;++ cnt[(unsigned)a+LEN];}int a = 0;int tmp = 0;for(;;){tmp += cnt[a];if(tmp > n / 2)break;++ a;}long long ans = a;ans += MID - LEN;cout << ans << endl;return 0;}