No.2977 Kth Xor Pair
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 49
作問者 :
nouka28
/ テスター :
👑 
p-adic
タグ : / 解いたユーザー数 49
作問者 :
nouka28
/ テスター :
👑 p-adic
問題文最終更新日: 2024-11-25 20:50:56
問題文
長さ $N$ の非負整数列 $A$ と正整数 $K$ が与えられます.
$A_i\oplus A_j\ (1\leq i< j\leq N)$ をすべて求め、それらを重複込みで昇順に並べたとき、その $K$ 番目の値を求めてください.
ただし、$\oplus$ で bitwise xor を表します.
制約
- $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$
- 入力はすべて整数
入力
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
出力
答えを出力してください.
サンプル
サンプル1
入力
5 7 0 1 2 3 4
出力
4
$A_i\oplus A_j\ (1\leq i< j\leq N)$ をすべて求め、それらを昇順に並べたとき、$(1, 1, 2, 2, 3, 3, 4, 5, 6, 7)$ になります.
よって、答えは $4$ となります.
サンプル2
入力
10 20 31 14 15 92 65 35 89 79 38 28
出力
60
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。