結果

問題 No.670 log は定数
コンテスト
ユーザー nebukuro09
提出日時 2018-04-08 00:07:54
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
AC  
実行時間 2,362 ms / 4,000 ms
+ 925µs
コード長 1,130 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 867 ms
コンパイル使用メモリ 127,488 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-26 07:17:42
合計ジャッジ時間 27,066 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/checkedint.d(814): Warning: cannot inline function `core.checkedint.mulu!().mulu`
ulong mulu()(ulong x, uint y, ref bool overflow)
      ^

ソースコード

diff #
raw source code 

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