AT_abc249_g [ABC249G] Xor Cards

题目描述

有 $N$ 张卡片，编号为 $1,\dots,N$。第 $i$ 张卡片的正面写有整数 $A_i$，背面写有整数 $B_i$。

你可以选择任意数量（至少一张）的卡片，使得所选卡片正面上的整数的异或和不超过 $K$。请你求出在满足条件的情况下，所选卡片背面上的整数的异或和的最大可能值。

异或和的定义如下：对于整数 $a,b$，它们的异或和 $a \oplus b$ 定义为：将 $a,b$ 用二进制表示后，每一位上只有一方为 $1$ 时该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制为 $011 \oplus 101 = 110$）。 一般地，$k$ 个整数 $p_1,\dots,p_k$ 的异或和定义为 $((\cdots((p_1 \oplus p_2) \oplus p_3)\oplus\cdots)\oplus p_k)$，并且可以证明其结果与顺序无关。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

输出格式

请输出满足条件的卡片选择方案中，所选卡片背面上的整数的异或和的最大值。如果无法满足条件，则输出 $-1$。

输入输出样例 #1

输入 #1

4 2
1 1
3 2
2 2
0 1

输出 #1

3

输入输出样例 #2

输入 #2

1 2
3 4

输出 #2

-1

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $1 \leq N \leq 1000$
• $0 \leq K < 2^{30}$
• $0 \leq A_i, B_i < 2^{30}\ (1 \leq i \leq N)$
• 输入均为整数

样例解释 1

选择卡片 $1,2$，正面整数的异或和为 $2$，背面整数的异或和为 $3$，这是最大值。

样例解释 2

无法选择满足条件的卡片。

由 ChatGPT 4.1 翻译