結果

問題 No.702 中央値を求めよ LIMITED
ユーザー amtgjwamtgjw
提出日時 2018-07-11 17:07:28
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 MLE -
testcase_20 MLE -
testcase_21 MLE -
testcase_22 MLE -
testcase_23 MLE -
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
権限があれば一括ダウンロードができます

ソースコード

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