問題一覧 > 通常問題

No.2977 Kth Xor Pair

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 56
作問者 : nouka28 / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11643 / 自分の提出
問題文最終更新日: 2024-11-25 20:50:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2024 (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of non-negative integers of length $N$ and a positive integer $K$.

Compute all values $A_i\oplus A_j\ (1\leq i< j\leq N)$ and sort them in ascending order, counting duplicates. Find the $K$-th value.

Here, $\oplus$ denotes bitwise xor.

Constraints

  • $2\leq N\leq 2\times 10^5$
  • $1\leq K\leq \displaystyle \frac{N(N-1)}{2}$
  • $0\leq A_i\leq 10^9$
  • All input values are integers

Input

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Output the answer.

Sample

Sample 1
Input
5 7
0 1 2 3 4
Output
4

Computing all values $A_i\oplus A_j\ (1\leq i< j\leq N)$ and sorting them in ascending order gives $(1, 1, 2, 2, 3, 3, 4, 5, 6, 7)$.

Therefore, the answer is $4$.

Sample 2
Input
10 20
31 14 15 92 65 35 89 79 38 28
Output
60

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。