No.2977 Kth Xor Pair
問題文最終更新日: 2024-11-25 20:50:56
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。