結果
問題 | No.670 log は定数 |
ユーザー | nebukuro09 |
提出日時 | 2018-04-08 00:07:54 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 2,562 ms / 4,000 ms |
コード長 | 1,130 bytes |
コンパイル時間 | 1,461 ms |
コンパイル使用メモリ | 152,224 KB |
実行使用メモリ | 7,120 KB |
最終ジャッジ日時 | 2023-09-03 19:14:59 |
合計ジャッジ時間 | 30,558 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,558 ms
5,024 KB |
testcase_01 | AC | 2,550 ms
5,088 KB |
testcase_02 | AC | 2,556 ms
5,012 KB |
testcase_03 | AC | 2,555 ms
5,008 KB |
testcase_04 | AC | 2,562 ms
7,120 KB |
testcase_05 | AC | 2,543 ms
6,796 KB |
testcase_06 | AC | 2,548 ms
5,052 KB |
testcase_07 | AC | 2,538 ms
5,068 KB |
testcase_08 | AC | 2,550 ms
5,040 KB |
testcase_09 | AC | 2,550 ms
4,984 KB |
ソースコード
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; }