102496: [AtCoder]ABC249 G - Xor Cards
Description
Score : $600$ points
Problem Statement
There are $N$ cards numbered $1, \dots, N$. Card $i \, (1 \leq i \leq N)$ has an integer $A_i$ written on the front and an integer $B_i$ written on the back.
Consider choosing one or more cards so that the exclusive logical sum of the integers written on the front of the chosen cards is at most $K$. Find the maximum possible exclusive logical sum of the integers written on the back of the chosen cards.
What is the exclusive logical sum?
The exclusive logical sum $a \oplus b$ of two integers $a$ and $b$ is defined as follows.- The $2^k$'s place ($k \geq 0$) in the binary notation of $a \oplus b$ is $1$ if exactly one of the $2^k$'s places in the binary notation of $a$ and $b$ is $1$; otherwise, it is $0$.
In general, the exclusive logical sum of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$. We can prove that it is independent of the order of $p_1, \dots, p_k$.
Constraints
- $1 \leq N \leq 1000$
- $0 \leq K \lt 2^{30}$
- $0 \leq A_i, B_i \lt 2^{30} \, (1 \leq i \leq N)$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$
Output
Print the maximum possible exclusive logical sum of the integers written on the back of the chosen cards when choosing one or more cards so that the exclusive logical sum of the integers written on the front of the chosen cards is at most $K$. If it is impossible to choose cards in such way, print $-1$ instead.
Sample Input 1
4 2 1 1 3 2 2 2 0 1
Sample Output 1
3
By choosing Cards $1$ and $2$, the exclusive logical sum of the integers written on the front of them is $2$, and that on the back of them is $3$, which is the maximum.
Sample Input 2
1 2 3 4
Sample Output 2
-1
It is impossible to choose cards so that the condition is satisfied.
Sample Input 3
10 326872757 487274679 568989827 267359104 968688210 669234369 189421955 1044049637 253386228 202278801 233212012 436646715 769734012 478066962 376960084 491389944 1033137442 214977048 1051768288 803550682 1053605300
Sample Output 3
1064164329
Input
题意翻译
给定 $n$ 个二元组 $(x_i,y_i)$ 构成的可重集 $S$，你需要选择 $S$ 的一个可重子集 $T$，满足 $\bigoplus \limits_{(x,y)\in T}x$ 不大于 $k$。 你需要最大化 $\bigoplus\limits_{(x,y)\in T} y$。若无解，输出 $-1$。 $n\le 1000, 0\le x_i,y_i,k < 2^{30}$。 translate by @[Dr_Gilbert](/user/574568)Output
问题描述
有$N$张编号为$1, \dots, N$的卡片。第$i \, (1 \leq i \leq N)$张卡片的正面写有整数$A_i$，背面写有整数$B_i$。
考虑选择一张或多张卡片，使得选择的卡片正面所写的整数的排他逻辑和（exclusive logical sum）不超过$K$。找出所选卡片背面所写的整数的最大可能排他逻辑和。
什么是排他逻辑和？
两个整数$a$和$b$的排他逻辑和$a \oplus b$定义如下。- 在$a \oplus b$的二进制表示中的第$2^k$位（$k \geq 0$）为$1$，如果$a$和$b$的二进制表示中的第$2^k$位有且仅有一个为$1$；否则，为$0$。
一般地，$k$个整数$p_1, \dots, p_k$的排他逻辑和定义为$(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$。我们可以证明它与$p_1, \dots, p_k$的顺序无关。
约束
- $1 \leq N \leq 1000$
- $0 \leq K \lt 2^{30}$
- $0 \leq A_i, B_i \lt 2^{30} \, (1 \leq i \leq N)$
- 输入中的所有值都是整数。
输入
从标准输入以以下格式获取输入：
$N$ $K$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$
输出
当选择的卡片正面所写的整数的排他逻辑和不超过$K$时，打印所选卡片背面所写的整数的最大可能排他逻辑和。如果无法以这种方式选择卡片，则打印$-1$代替。
样例输入1
4 2 1 1 3 2 2 2 0 1
样例输出1
3
选择卡片$1$和$2$时，它们正面所写的整数的排他逻辑和为$2$，背面所写的整数的排他逻辑和为$3$，这是最大的可能值。
样例输入2
1 2 3 4
样例输出2
-1
无法选择满足条件的卡片。
样例输入3
10 326872757 487274679 568989827 267359104 968688210 669234369 189421955 1044049637 253386228 202278801 233212012 436646715 769734012 478066962 376960084 491389944 1033137442 214977048 1051768288 803550682 1053605300
样例输出3
1064164329