結果
問題 |
No.702 中央値を求めよ LIMITED
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)); } }