結果

問題 No.670 log は定数
コンテスト
ユーザー nebukuro09
提出日時 2018-04-08 00:07:54
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2,459 ms / 4,000 ms
コード長 1,130 bytes
コンパイル時間 1,455 ms
コンパイル使用メモリ 153,068 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-13 00:18:55
合計ジャッジ時間 28,064 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

ulong seed;
int next() {
    seed = seed ^ (seed << 13);
    seed = seed ^ (seed >> 7);
    seed = seed ^ (seed << 17);
    return cast(int)(seed >> 33);
}

void main() {
    immutable long M = 2L ^^ 31;
    immutable long T = 20000;

    int N, Q;
    readf("%d %d %d\n", &N, &Q, &seed);
    foreach (i; 0..10000) next();

    long[] A = new long[N];
    foreach (i; 0..N) A[i] = next();
    A.sort();

    long[] B = new long[M/T+10];

    for (long i = 0, p = 0; i * T <= M+1; ++i) {
        while (p < N && A[p.to!int] < i * T) ++p;
        B[i.to!int] = p;
    }

    long ans = 0;
    foreach (i; 0..Q) {
        long q = next();
        long a = q - q % T;
        long b = q - q % T + T;
        if (B[a/T] == B[b/T]) {
            ans ^= B[a/T] * i;
        } else {
            long tmp = B[a/T];
            for (long j = B[a/T]; j < N && A[j] < q; ++j) ++tmp;
            ans ^= tmp * i;
        }
    }

    ans.writeln;
}
0