結果

問題 No.702 中央値を求めよ LIMITED
ユーザー 37zigen
提出日時 2018-06-16 02:10:13
言語 Java
(openjdk 23)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,543 bytes
コンパイル時間 2,294 ms
コンパイル使用メモリ 77,640 KB
実行使用メモリ 41,892 KB
最終ジャッジ日時 2024-12-26 04:44:44
合計ジャッジ時間 61,238 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 2
other MLE * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        new Main().run();
    }
    void run() throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        seed = sc.nextLong();
        initialize();
        int n = 10000001;
        int[] a = new int[1 << 16];
        for (int i = 0; i < 10000001; ++i) {
            ++a[(int) (generate() >> 16)];
        }
        int sum = 0;
        int p = 0;
        while (sum < 5000001) {
            sum += a[p];
            ++p;
        }
        p = p - 1;
        long gt = Math.max(0, (1 << 16) * (p - 1)), el = Math.min((long) (1L << 16) * (p + 1), (1L << 32) - 1);
        while (true) {
            long m = (gt + el) / 2;
            initialize();
            for (int i = 0; i < 10000001; ++i) {
                generate();
                if (w < m)
                    ++c1;
                else if (w == m)
                    ++c2;
                else
                    ++c3;
            }
            if (c1 + c2 < 5000001) {
                gt = m;
            } else {
                el = m;
            }
            if (c1 + c2 >= 5000001 && c2 + c3 >= 5000001) {
                System.out.println(m);
                return;
            }
        }
    }
    long c1 = 0, c2 = 0, c3 = 0;
    long x = 0, y = 1, z = 2, w = 3;
    long seed;
    void initialize() {
        x = seed;
        y = 1;
        z = 2;
        w = 3;
        c1 = 0;
        c2 = 0;
        c3 = 0;
    }
    long generate() {
        long t = (x ^ (x << 11)) & ((1L << 32) - 1);
        x = y & ((1L << 32) - 1);
        y = z & ((1L << 32) - 1);
        z = w & ((1L << 32) - 1);
        w = ((w ^ (w >> 19)) ^ (t ^ (t >> 8))) & ((1L << 32) - 1);
        return w;
    }
    void tr(Object... objects) {
        System.out.println(Arrays.deepToString(objects));
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0