310560: CF1851F. Lisa and the Martians
Description
Lisa was kidnapped by martians! It okay, because she has watched a lot of TV shows about aliens, so she knows what awaits her. Let's call integer martian if it is a non-negative integer and strictly less than $2^k$, for example, when $k = 12$, the numbers $51$, $1960$, $0$ are martian, and the numbers $\pi$, $-1$, $\frac{21}{8}$, $4096$ are not.
The aliens will give Lisa $n$ martian numbers $a_1, a_2, \ldots, a_n$. Then they will ask her to name any martian number $x$. After that, Lisa will select a pair of numbers $a_i, a_j$ ($i \neq j$) in the given sequence and count $(a_i \oplus x) \& (a_j \oplus x)$. The operation $\oplus$ means Bitwise exclusive OR, the operation $\&$ means Bitwise And. For example, $(5 \oplus 17) \& (23 \oplus 17) = (00101_2 \oplus 10001_2) \& (10111_2 \oplus 10001_2) = 10100_2 \& 00110_2 = 00100_2 = 4$.
Lisa is sure that the higher the calculated value, the higher her chances of returning home. Help the girl choose such $i, j, x$ that maximize the calculated value.
InputThe first line contains an integer $t$ ($1 \le t \le 10^4$) — number of testcases.
Each testcase is described by two lines.
The first line contains integers $n, k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le 30$) — the length of the sequence of martian numbers and the value of $k$.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^k$) — a sequence of martian numbers.
It is guaranteed that the sum of $n$ over all testcases does not exceed $2 \cdot 10^5$.
OutputFor each testcase, print three integers $i, j, x$ ($1 \le i, j \le n$, $i \neq j$, $0 \le x < 2^k$). The value of $(a_i \oplus x) \& (a_j \oplus x)$ should be the maximum possible.
If there are several solutions, you can print any one.
ExampleInput10 5 4 3 9 1 4 13 3 1 1 0 1 6 12 144 1580 1024 100 9 13 4 3 7 3 0 4 3 2 0 0 1 2 4 12 2 9 4 6 14 9 4 4 4 5 10 2 2 1 1 0 2 4 11 4 9 4 2 11 10 1 6 9 11 0 5Output
1 3 14 1 3 0 5 6 4082 2 3 7 1 2 3 1 2 15 4 5 11 1 2 0 1 2 0 2 7 4Note
First testcase: $(3 \oplus 14) \& (1 \oplus 14) = (0011_2 \oplus 1110_2) \& (0001_2 \oplus 1110_2) = 1101_2 = 1101_2 \& 1111_2 = 1101_2 = 13$.
Second testcase: $(1 \oplus 0) \& (1 \oplus 0) = 1$.
Third testcase: $(9 \oplus 4082) \& (13 \oplus 4082) = 4091$.
Fourth testcase: $(3 \oplus 7) \& (0 \oplus 7) = 4$.
Input
题意翻译
给定长度为 $n$ 的序列 $a$ 和一个正整数 $k$，保证 $0\leq a_i< 2^k$。求满足 $0\leq x<2^k$ 且 $i\neq j$ 的三元组 $(i,j,x)$ 使得 $(a_i\oplus x)\operatorname{and}(a_j\oplus x)$ 最大。如果有多组符合要求的输出任意一组即可。 多组数据。Output
外星人会给丽莎 $n$ 个“火星整数”$a_1, a_2, \ldots, a_n$。然后他们会要求她命名任何一个“火星整数”$x$。之后，丽莎将选择给定序列中的一对数字 $a_i, a_j$ ($i \neq j$) 并计算 $(a_i \oplus x) \& (a_j \oplus x)$。运算 $\oplus$ 表示按位异或，运算 $\&$ 表示按位与。例如，$(5 \oplus 17) \& (23 \oplus 17) = (00101_2 \oplus 10001_2) \& (10111_2 \oplus 10001_2) = 10100_2 \& 00110_2 = 00100_2 = 4$。
丽莎确信计算出的值越高，她回家的机会就越大。帮助这个女孩选择这样的 $i, j, x$，以使计算出的值最大化。
**输入数据格式**：
第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。
每个测试用例由两行描述。
第一行包含整数 $n, k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le 30$) —— “火星整数”序列的长度和 $k$ 的值。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^k$) —— 一个“火星整数”序列。
保证所有测试用例中 $n$ 的总和 **不超过** $2 \cdot 10^5$。
**输出数据格式**：
对于每个测试用例，打印三个整数 $i, j, x$ ($1 \le i, j \le n$, $i \neq j$, $0 \le x < 2^k$)。$ (a_i \oplus x) \& (a_j \oplus x) $ 的值应该是尽可能大的。
如果有多个解，可以打印任何一个。丽莎被火星人绑架了！没关系，因为她看过很多关于外星人的电视节目，所以她知道等待她的是什么。我们将整数称为“火星整数”，如果它是一个非负整数，并且严格小于 $2^k$，例如，当 $k = 12$ 时，数字 51、1960、0 是“火星整数”，而数字 $\pi$、-1、$\frac{21}{8}$、4096 不是。 外星人会给丽莎 $n$ 个“火星整数”$a_1, a_2, \ldots, a_n$。然后他们会要求她命名任何一个“火星整数”$x$。之后，丽莎将选择给定序列中的一对数字 $a_i, a_j$ ($i \neq j$) 并计算 $(a_i \oplus x) \& (a_j \oplus x)$。运算 $\oplus$ 表示按位异或，运算 $\&$ 表示按位与。例如，$(5 \oplus 17) \& (23 \oplus 17) = (00101_2 \oplus 10001_2) \& (10111_2 \oplus 10001_2) = 10100_2 \& 00110_2 = 00100_2 = 4$。 丽莎确信计算出的值越高，她回家的机会就越大。帮助这个女孩选择这样的 $i, j, x$，以使计算出的值最大化。 **输入数据格式**： 第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。 每个测试用例由两行描述。 第一行包含整数 $n, k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le 30$) —— “火星整数”序列的长度和 $k$ 的值。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^k$) —— 一个“火星整数”序列。 保证所有测试用例中 $n$ 的总和 **不超过** $2 \cdot 10^5$。 **输出数据格式**： 对于每个测试用例，打印三个整数 $i, j, x$ ($1 \le i, j \le n$, $i \neq j$, $0 \le x < 2^k$)。$ (a_i \oplus x) \& (a_j \oplus x) $ 的值应该是尽可能大的。 如果有多个解，可以打印任何一个。