No.670 log は定数

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 44
作問者 : yosupotyosupot / テスター : sigma425sigma425

1 ProblemId : 1886 / 出題時の順位表

問題文


長さ $N$ の数列 $a_i$ に $Q$ 個のクエリが与えられます。それぞれのクエリは以下のようなクエリです。

  • $x$ が与えられるので、${a_i}$ の要素のうち $x$ より小さいものの個数を求めてください

なお、数列、クエリの個数は入力で与えられますが、その内容は共に乱数生成器により生成されます。

また、出力は $i(i = 1,2,...,Q)$ 個目のクエリの結果を $r_i$ として、
$r_i \times (i-1)$ をすべてxorしたものを出力してください。

つまり、$s_i = r_i \times (i-1)$ として、$s_1 \oplus s_2 \oplus ... \oplus s_Q$ を出力して下さい。

なお、クエリの結果をまとめているのは、出力にかかる時間を減らすためです(想定解では、すべてのクエリに対する答えを得ています)

C++、Java、D、3つの言語について、この問題の愚直解(非常に長い時間実行する必要があるが、正しい答えを出力するコード)を載せるので、入力の生成方法はこれを参考にしてください。なお、この3つの言語については時間制限に間に合う想定解があります。(C++: 1461ms, Java: 3627ms(は?), D:2721ms)

ソースコード

入力

N Q Seed


$N = 2 \times 10^5$
$Q = 5 \times 10^7$
$1 \leq Seed \leq 10^9$
$0 \leq a_i, x \leq 2^{31} - 1$

出力

最後に改行してください。

サンプル

サンプル1
入力
3 5 100
出力
11

$\{a_i\} = \{574298591, 668652393, 1255298759\}$、クエリの内容は順に
$1374848783, 844241532, 121207337, 1805629405, 534777954$となります。

このケースは入力の制約を満たしません。

サンプル2
入力
50000 100000 1194
出力
5935406007

載せた愚直解でもこのサイズならば動きます。(数十秒かかるかもしれません)

このケースも入力の制約を満たしません。

サンプル3
入力
200000 50000000 2525
出力
4959527808339

載せた愚直解にこのケースを入れると、コンテストが終わるまでに結果が返ってくるか怪しいと思います。気を付けてください。

このケースは入力の制約を満たします。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。