Algoogle

Algorithm for Programming Contest

AOJ 2527 MLE

Category: AOJ Tag: sqrt-decomposition

MLE

問題概要


擬似乱数を生成するコードがある.
これによって初期値x0でn個の乱数を生成するときk番目の値はいくらか.

解法


生成される乱数を適当な大きさの区間で分ける.
そうするとk番目の値を含む区間がわかるので, もう一度乱数を生成して求めた区間の数だけ集める.
あとはそれをソートしてやればk番目の値がわかる.
10^8ぐらいの計算量になるが操作が軽いので問題なく間にあう.

コード


(2527.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
const ull d = ULLONG_MAX/1024;
const ull llm = LLONG_MAX;

int n, k, x0, cnt[1024];

void rnd(ull &x){
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
}

ll solve(){
    if(!x0) return 0;
    ull x = x0;
    rep(i,n){
        cnt[(ull)(x+llm)/d]++;
        rnd(x);
    }
    int sum = 0, pos = 0;
    rep(i,1024){
        if(sum+cnt[i] >= k){
            pos = i;
            k -= sum+1;
            break;
        }
        sum += cnt[i];
    }
    vector<ll> a;
    x = x0;
    rep(i,n){
        if((ull)(x+llm)/d == (ull)pos) a.pb(x);
        rnd(x);
    }
    sort(all(a));
    return a[k];
}

int main(){
    cin >> n >> k >> x0;
    cout << solve() << endl;
    return 0;
}

Comments