結果

問題 No.702 中央値を求めよ LIMITED
ユーザー amtgjw
提出日時 2018-07-11 17:07:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,199 bytes
コンパイル時間 688 ms
コンパイル使用メモリ 79,076 KB
実行使用メモリ 42,624 KB
最終ジャッジ日時 2024-09-19 18:57:04
合計ジャッジ時間 2,609 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 2
other MLE * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <math.h>
#include <cstring>

using namespace std;

#define REP(i,n)	for(int i=0;i<(n);++i)
#define REPS(i,s,t)	for(int i=(s);i<(t);++i)

#define INF 		2000000007
#define MOD			998244353

#define MAX 		100005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int ll;

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

ll quick(uint *a,ll t,ll left,ll right){
	while(left <= right){
		if(a[left] < a[t]){
			swap(a[left],a[t]);
			t = left,left++;
		}
		else if(a[right] > a[t]){
			right--;
		}
		else{
			swap(a[left],a[right]);
			swap(a[left],a[t]);
			t++,left++;
		}
	}
	return t;
}

uint a[10000001];
int main(void) {
    ll seed; cin >> seed; 
    x = seed;
    
    for (int i = 0; i < 10000001; i++) {
        a[i] = generate();
    }

	ll t=0;
	ll l=1,r=10;
	while((t=quick(a,t,l,r))!=5000000){
		if(t < 5000000){t++;l=t+1;}
		else{r=t-1;t=l,l=t+1;}
	}
	cout << a[t] << endl;//*/

    return 0;
}
0