AT_arc184_a.[ARC184A] Appraiser

本题为交互式问题，且评测器为自适应（adaptive）。详情请参阅注意事项。
此外，题目中的参数固定为 $N=1000, M=10, Q=950$。

有 $N$ 枚硬币，编号为 $1,2,\dots,N$。
在这些硬币中，恰好有 $M$ 枚是假币。

鉴定师每次可以鉴定两枚硬币，判断它们是否为同一类型。具体来说：

• 如果两枚硬币“都是正品”或“都是假币”，则判定为同种。
• 否则，判定为异种。

请在不超过 $Q$ 次的鉴定内，找出所有假币。

本题为交互式问题。
首先，从标准输入读入 $N, M, Q$。

$N$ $M$ $Q$

接下来，你可以进行 $0$ 次或多次（最多 $Q$ 次）鉴定。

每次鉴定时，请按如下格式输出到标准输出，表示要鉴定硬币 $x, y$。（末尾需换行）

? $x$ $y$

其中，$x, y$ 是 $1$ 到 $N$ 之间的不同整数。

评测器会返回以下三种之一的响应：

0

当响应为 0 时，表示硬币 $x, y$ 为同种。

1

当响应为 1 时，表示硬币 $x, y$ 为异种。

-1

当响应为 -1 时，表示鉴定无效。具体包括：

• 输出的 $x, y$ 不满足约束条件
• 鉴定次数超过 $Q$ 次

只要出现上述任一情况，评测器会返回 -1，此时你的程序已被判为不正确，请立即退出。

最后，请按如下格式输出，表示你认为硬币 $A_1, A_2, \dots, A_M$ 是假币。（末尾需换行）

! $A_1$ $A_2$ $\dots$ $A_M$

其中，$A_i$ 是 $1$ 到 $N$ 之间的不同整数。
输出后，请立即退出程序。

注意，若输出格式不符合要求，也会被判为不正确。此后会返回 -1，此时也请立即退出程序。

（同上，见输入格式）

约束条件

• $ \color{red}{N = 1000} $
• $ \color{red}{M = 10} $
• $ \color{red}{Q = 950} $

注意事项

• 每次输出后，需在末尾加换行并刷新标准输出。 否则可能会被判为 TLE 或 WA。
• 输出答案后（或收到 -1 时）请立即退出程序，否则评测结果不确定。
• 多余的换行也会被视为输出格式错误。
• 本题评测器为自适应（adaptive）。也就是说，评测器可以在任何时刻，只要保证一致性，就可以更改其假币的设定。详见输入输出样例。

输入输出样例

本样例中 $N=5, M=2, Q=10$，评测器最初假定硬币 $1,2$ 为假币。

注意，本样例不满足本题约束，仅用于说明，不会用于实际评测。

输入输出说明
5 2 10
给出 $N, M, Q$。
? 1 2
鉴定硬币 $1,2$。
0
判定为同种。
? 1 3
鉴定硬币 $1,3$。
1
判定为异种。
? 1 4
鉴定硬币 $1,4$。
1
判定为异种。
! 1 2
输出 $1,2$ 为假币。实际上，评测器最初假定 $1,2$ 为假币，但假如 $3,4$ 也能与之前的所有判定结果一致，评测器也可以将假币设定更改为 $3,4$。
因此，评测器有可能判定你的解答不正确。

由 ChatGPT 4.1 翻译