Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個の宝石があります。i 番目の宝石は色が D_i で美しさが V_i です。
ここで、色は 1,2,\ldots,C のいずれかであり、どの色の宝石も少なくとも 1 個存在します。
N 個の宝石から、色が相異なる C 個の宝石を選んでネックレスを作ります。(選ぶ順番は考えません。) ネックレスの美しさは選んだ宝石の美しさのビットごとの \rm XOR となります。
全てのありえるネックレスの作り方のうち、美しさが K 番目に大きいもののネックレスの美しさを求めてください。(同じ美しさの作り方が複数存在する場合、それらは全て数えます。)
ビットごとの \rm XOR とは
整数 A, B のビットごとの \rm XOR 、A\ {\rm XOR}\ B は、以下のように定義されます。- A\ {\rm XOR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 1 \leq C \leq N \leq 70
- 1 \leq D_i \leq C
- 0 \leq V_i < 2^{60}
- 1 \leq K \leq 10^{18}
- 少なくとも K 種類のネックレスを作ることができる
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N C K D_1 V_1 \vdots D_N V_N
出力
答えを出力せよ。
入力例 1
4 2 3 2 4 2 6 1 2 1 3
出力例 1
5
以下のような 4 種類のネックレスを作ることができます。
- 1,3 番目の宝石を選ぶ。ネックレスの美しさは 4\ {\rm XOR}\ 2 =6 となる。
- 1,4 番目の宝石を選ぶ。ネックレスの美しさは 4\ {\rm XOR}\ 3 =7 となる。
- 2,3 番目の宝石を選ぶ。ネックレスの美しさは 6\ {\rm XOR}\ 2 =4 となる。
- 2,4 番目の宝石を選ぶ。ネックレスの美しさは 6\ {\rm XOR}\ 3 =5 となる。
よって美しさが 3 番目に大きいネックレスの美しさは 5 となります。
入力例 2
3 1 2 1 0 1 0 1 0
出力例 2
0
3 種類のネックレスを作ることができ、いずれも美しさは 0 です。
入力例 3
10 3 11 1 414213562373095048 1 732050807568877293 2 236067977499789696 2 449489742783178098 2 645751311064590590 2 828427124746190097 3 162277660168379331 3 316624790355399849 3 464101615137754587 3 605551275463989293
出力例 3
766842905529259824
Score : 600 points
Problem Statement
We have N gemstones. The color and beauty of the i-th gemstone are D_i and V_i, respectively.
Here, the color of each gemstone is one of 1, 2, \ldots, C, and there is at least one gemstone of each color.
Out of the N gemstones, we will choose C with distinct colors and use them to make a necklace. (The order does not matter.) The beautifulness of the necklace will be the bitwise \rm XOR of the chosen gemstones.
Among all possible ways to make a necklace, find the beautifulness of the necklace made in the way with the K-th greatest beautifulness. (If there are multiple ways with the same beautifulness, we count all of them.)
What is bitwise \rm XOR?
The bitwise \rm XOR of integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
Constraints
- 1 \leq C \leq N \leq 70
- 1 \leq D_i \leq C
- 0 \leq V_i < 2^{60}
- 1 \leq K \leq 10^{18}
- There are at least K ways to make a necklace.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C K D_1 V_1 \vdots D_N V_N
Output
Print the answer.
Sample Input 1
4 2 3 2 4 2 6 1 2 1 3
Sample Output 1
5
There are four ways to make a necklace, as follows.
- Choose the 1-st and 3-rd gemstones to make a necklace with the beautifulness of 4\ {\rm XOR}\ 2 =6.
- Choose the 1-st and 4-th gemstones to make a necklace with the beautifulness of 4\ {\rm XOR}\ 3 =7.
- Choose the 2-nd and 3-rd gemstones to make a necklace with the beautifulness of 6\ {\rm XOR}\ 2 =4.
- Choose the 2-nd and 4-th gemstones to make a necklace with the beautifulness of 6\ {\rm XOR}\ 3 =5.
Thus, the necklace with the 3-rd greatest beautifulness has the beautifulness of 5.
Sample Input 2
3 1 2 1 0 1 0 1 0
Sample Output 2
0
There are three ways to make a necklace, all of which result in the beautifulness of 0.
Sample Input 3
10 3 11 1 414213562373095048 1 732050807568877293 2 236067977499789696 2 449489742783178098 2 645751311064590590 2 828427124746190097 3 162277660168379331 3 316624790355399849 3 464101615137754587 3 605551275463989293
Sample Output 3
766842905529259824