「TAOI-1」Antipathy World

> 簡単なことも解らないわ \ > あたしって何だっけ \ > それすら夜の手に絆されて \ > 愛のように 消える 消える \ > さようならも言えぬ儘泣いた フォニイ フォニイ フォニイ \ > 嘘に絡まっているあたしはフォニイ \ > **ANTIPATHY WORLD**

**这是一道 IO 交互题。** 可不有 $n$ 朵花，每朵花有一个正整数美丽度。 她发现，有一朵花的美丽度不小于其它任何一朵花的美丽度的两倍。 你想知道这朵花是哪一朵，于是你可以进行至多 $k$ 次询问，每次询问你给出两个正整数 $i,j \in [1, n]$，可不会告诉你第 $i$ 朵和第 $j$ 朵花的美丽度之差的绝对值。 你想运用这些询问的答案，得到最美丽的花是第几朵。 ### 交互格式 **本题有多组数据**。 第一行交互库给出一个整数 $T$，表示数据组数。 对于每组数据，第一行输入两个正整数 $n,k$。 对于你的每组询问，你输出 `? i j`，交互库会返回一个非负整数，表示第 $i$ 朵和第 $j$ 朵花的美丽度之差。 如果你已经得到答案，输出 `! i` 代表你得到第 $i$ 朵花为最美丽的花。在此之后你应该开始对下一组数据的处理。 每次你输出之后，请**刷新缓冲区**。 你可以使用如下语句来清空缓冲区： - 对于 C/C++：`fflush(stdout)`； - 对于 C++：`std::cout << std::flush`； - 对于 Java：`System.out.flush()`； - 对于 Python：`stdout.flush()`； - 对于 Pascal：`flush(output)`； - 对于其他语言，请自行查阅对应语言的帮助文档。 特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

见「交互格式」。

见「交互格式」。

1
3 114514

3

2

1

? 1 2

? 1 3

? 2 3

! 1

样例中给出了一种可能的交互方式，其中花的美丽度为 $\{4,1,2\}$。 --- **本题采用捆绑测试**。 - Subtask 1（20 points）：$k=\dfrac{n(n-1)}{2}$，$n \le 200$。 - Subtask 2（30 points）：$k=n$。 - Subtask 3（50 points）：$k=\left\lfloor\dfrac{n}{2}\right\rfloor+2$。 对于所有测试数据，设所有花的美丽度为 $a_i$，$1 \le T \le 25$，$3 \le n \le 5 \times 10^4$，$1 \le a_i \le 10^8$。