P311112 - CF1936A. Bitwise Operation Wizard - SSOJ

Memory Limit：256 MB Time Limit：2 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

A. Bitwise Operation Wizardtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

There is a secret sequence $p_0, p_1, \ldots, p_{n-1}$, which is a permutation of $\{0,1,\ldots,n-1\}$.

You need to find any two indices $i$ and $j$ such that $p_i \oplus p_j$ is maximized, where $\oplus$ denotes the bitwise XOR operation.

To do this, you can ask queries. Each query has the following form: you pick arbitrary indices $a$, $b$, $c$, and $d$ ($0 \le a,b,c,d < n$). Next, the jury calculates $x = (p_a \mid p_b)$ and $y = (p_c \mid p_d)$, where $|$ denotes the bitwise OR operation. Finally, you receive the result of comparison between $x$ and $y$. In other words, you are told if $x < y$, $x > y$, or $x = y$.

Please find any two indices $i$ and $j$ ($0 \le i,j < n$) such that $p_i \oplus p_j$ is maximum among all such pairs, using at most $3n$ queries. If there are multiple pairs of indices satisfying the condition, you may output any one of them.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

Interaction

The first line of each test case contains one integer $n$ ($2 \le n \le 10^4$). At this moment, the permutation $p_0, p_1, \ldots, p_{n-1}$ is chosen. The interactor in this task is not adaptive. In other words, the sequence $p$ is fixed in every test case and does not change during the interaction.

To ask a query, you need to pick four indices $a$, $b$, $c$, and $d$ ($0 \le a,b,c,d < n$) and print the line of the following form:

"? a b c d"

After that, you receive:

"<" if $(p_a \mid p_b) < (p_c \mid p_d)$;
"=" if $(p_a \mid p_b) = (p_c \mid p_d)$;
">" if $(p_a \mid p_b) > (p_c \mid p_d)$.

You can make at most $3n$ queries of this form.

Next, if your program has found a pair of indices $i$ and $j$ ($0 \le i, j < n$) such that $p_i \oplus p_j$ is maximized, print the line of the following form:

"! i j"

Note that this line is not considered a query and is not taken into account when counting the number of queries asked.

After this, proceed to the next test case.

If you make more than $3n$ queries during an interaction, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query or the answer for a test case, do not forget to output the end of line and flush the output. Otherwise, you will get the verdict Idleness Limit Exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see the documentation for other languages.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

Hacks

To hack, follow the test format below.

The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \le n \le 10^4$).

The second line of each test case contains $n$ integers $p_0,p_1,\ldots,p_{n-1}$, which represent a permutation of integers from $0$ to $n - 1$.

The sum of $n$ over all test cases should not exceed $10^4$.

ExampleInput

Output

Note

In the first test case, the hidden permutation is $p=[0,3,1,2]$.

For the query "? 0 2 3 1", the jury return "<" because $(p_0 \mid p_2) = (0 \mid 1) =1 < (p_3 \mid p_1) = (2 \mid 3) = 3$.

For the query "? 1 1 2 3", the jury return "=" because $(p_1 \mid p_1) = (3\mid 3)= 3 = (p_2 \mid p_3) = (1 \mid 2)=3$.

For the query "? 1 2 0 3", the jury return ">" because $(p_1 \mid p_2) = (3 \mid 1) = 3 > (p_0 \mid p_3) = (0\mid 2)=2$.

The answer $i = 3$ and $j = 2$ is valid: $(p_3 \oplus p_2) = (2 \oplus 1) = 3$ is indeed equal to the maximum possible value of $p_i \oplus p_j$. Another valid answer would be $i=0$ and $j=1$. As the number of queries does not exceed $3n=12$, the answer is considered correct.

In the second test case, $n = 2$, so $p$ is either $[0, 1]$ or $[1, 0]$. In any case, $p_0 \oplus p_1 = 1$ is maximum possible.

题目大意：这是一个交互式问题。有一个秘密序列 $ p_0, p_1, \ldots, p_{n-1} $，它是 $\{0,1,\ldots,n-1\}$ 的一个排列。你需要找到任意两个索引 $ i $ 和 $ j $，使得 $ p_i \oplus p_j $ 最大化，其中 $ \oplus $ 表示按位异或操作。

为了做到这一点，你可以提出查询。每个查询的形式如下：你任意选择索引 $ a $, $ b $, $ c $, $ d $ ($ 0 \le a,b,c,d < n $)。然后，裁判计算 $ x = (p_a | p_b) $ 和 $ y = (p_c | p_d) $，其中 $ | $ 表示按位或操作。最后，你收到 $ x $ 和 $ y $ 之间比较的结果。换句话说，你会被告知 $ x < y $，$ x > y $，还是 $ x = y $。

请使用最多 $ 3n $ 次查询找到使得 $ p_i \oplus p_j $ 最大的任意两个索引 $ i $ 和 $ j $ ($ 0 \le i,j < n $)。如果有多个满足条件的索引对，你可以输出其中任何一个。

输入输出数据格式：每个测试包含多个测试用例。第一行包含测试用例数 $ t $ ($ 1 \le t \le 10^3 $)。接下来是测试用例的描述。

交互：每个测试用例的第一行包含一个整数 $ n $ ($ 2 \le n \le 10^4 $)。此时，选择排列 $ p_0, p_1, \ldots, p_{n-1} $。此任务中的交互器是**非自适应的**。换句话说，序列 $ p $ 在每个测试用例中都是固定的，在交互过程中不会改变。

要提出查询，你需要选择四个索引 $ a $, $ b $, $ c $, $ d $ ($ 0 \le a,b,c,d < n $) 并打印以下形式的行：

```
? a b c d
```

之后，你会收到：

- 如果 $ (p_a | p_b) < (p_c | p_d) $，则返回 `"<"`
- 如果 $ (p_a | p_b) = (p_c | p_d) $，则返回 `"="`
- 如果 $ (p_a | p_b) > (p_c | p_d) $，则返回 `">"`

你可以进行最多 $ 3n $ 次此类查询。

如果程序找到了一对索引 $ i $ 和 $ j $ ($ 0 \le i, j < n $) 使得 $ p_i \oplus p_j $ 最大化，请打印以下形式的行：

```
! i j
```

注意，这行**不是**查询，并且**不计入**查询次数的统计。之后，继续进行下一个测试用例。

如果在交互过程中进行了超过 $ 3n $ 次查询，你的程序必须立即终止，并且你将收到 `Wrong Answer` 的结果。否则，你可以得到任意结果，因为你的解决方案将继续从已关闭的流中读取。

在打印查询或测试用例的答案后，不要忘记输出行尾并刷新输出。否则，你将得到 `Idleness Limit Exceeded` 的结果。为此，请使用：

- 在 C++ 中：`fflush(stdout)` 或 `cout.flush()`
- 在 Java 中：`System.out.flush()`
- 在 Pascal 中：`flush(output)`
- 在 Python 中：`stdout.flush()`
- 其他语言的文档中有说明。

保证所有测试用例的 $ n $ 之和不超过 $ 10^4 $。

**注意**：在第一个测试用例中，隐藏的排列是 $ p=[0,3,1,2] $。对于查询 `? 0 2 3 1`，裁判返回 `<`，因为 $ (p_0 | p_2) = (0 | 1) = 1 < (p_3 | p_1) = (2 | 3) = 3 $。对于查询 `? 1 1 2 3`，裁判返回 `=`，因为 $ (p_1 | p_1) = (3 | 3) = 3 = (p_2 | p_3) = (1 | 2) = 3 $。对于查询 `? 1 2 0 3`，裁判返回 `>`，因为 $ (p_1 | p_2) = (3 | 1) = 3 > (p_0题目大意：这是一个交互式问题。有一个秘密序列 \( p_0, p_1, \ldots, p_{n-1} $，它是 $\{0,1,\ldots,n-1\}$ 的一个排列。你需要找到任意两个索引 $ i $ 和 $ j $，使得 $ p_i \oplus p_j $ 最大化，其中 $ \oplus $ 表示按位异或操作。为了做到这一点，你可以提出查询。每个查询的形式如下：你任意选择索引 $ a $, $ b $, $ c $, $ d $ ($ 0 \le a,b,c,d < n $)。然后，裁判计算 $ x = (p_a | p_b) $ 和 $ y = (p_c | p_d) $，其中 $ | $ 表示按位或操作。最后，你收到 $ x $ 和 $ y $ 之间比较的结果。换句话说，你会被告知 $ x < y $，$ x > y $，还是 $ x = y $。请使用最多 $ 3n $ 次查询找到使得 $ p_i \oplus p_j $ 最大的任意两个索引 $ i $ 和 $ j $ ($ 0 \le i,j < n $)。如果有多个满足条件的索引对，你可以输出其中任何一个。输入输出数据格式：每个测试包含多个测试用例。第一行包含测试用例数 $ t $ ($ 1 \le t \le 10^3 $)。接下来是测试用例的描述。交互：每个测试用例的第一行包含一个整数 $ n $ ($ 2 \le n \le 10^4 $)。此时，选择排列 $ p_0, p_1, \ldots, p_{n-1} $。此任务中的交互器是**非自适应的**。换句话说，序列 $ p $ 在每个测试用例中都是固定的，在交互过程中不会改变。要提出查询，你需要选择四个索引 $ a $, $ b $, $ c $, $ d $ ($ 0 \le a,b,c,d < n $) 并打印以下形式的行： ``` ? a b c d ``` 之后，你会收到： - 如果 $ (p_a | p_b) < (p_c | p_d) $，则返回 `"<"` - 如果 $ (p_a | p_b) = (p_c | p_d) $，则返回 `"="` - 如果 $ (p_a | p_b) > (p_c | p_d) $，则返回 `">"` 你可以进行最多 $ 3n $ 次此类查询。如果程序找到了一对索引 $ i $ 和 $ j $ ($ 0 \le i, j < n $) 使得 $ p_i \oplus p_j $ 最大化，请打印以下形式的行： ``` ! i j ``` 注意，这行**不是**查询，并且**不计入**查询次数的统计。之后，继续进行下一个测试用例。如果在交互过程中进行了超过 $ 3n $ 次查询，你的程序必须立即终止，并且你将收到 `Wrong Answer` 的结果。否则，你可以得到任意结果，因为你的解决方案将继续从已关闭的流中读取。在打印查询或测试用例的答案后，不要忘记输出行尾并刷新输出。否则，你将得到 `Idleness Limit Exceeded` 的结果。为此，请使用： - 在 C++ 中：`fflush(stdout)` 或 `cout.flush()` - 在 Java 中：`System.out.flush()` - 在 Pascal 中：`flush(output)` - 在 Python 中：`stdout.flush()` - 其他语言的文档中有说明。保证所有测试用例的 $ n $ 之和不超过 $ 10^4 $。 **注意**：在第一个测试用例中，隐藏的排列是 $ p=[0,3,1,2] $。对于查询 `? 0 2 3 1`，裁判返回 `<`，因为 $ (p_0 | p_2) = (0 | 1) = 1 < (p_3 | p_1) = (2 | 3) = 3 $。对于查询 `? 1 1 2 3`，裁判返回 `=`，因为 $ (p_1 | p_1) = (3 | 3) = 3 = (p_2 | p_3) = (1 | 2) = 3 $。对于查询 `? 1 2 0 3`，裁判返回 `>`，因为 \( (p_1 | p_2) = (3 | 1) = 3 > (p_0

Codeforces Round 930 (Div. 1) - bitmasks - greedy - interactive - math - *1700

311112: CF1936A. Bitwise Operation Wizard

Description

Output

Source/Category

加入题单