AT_arc184_a [ARC184A] Appraiser

[problemUrl]: https://atcoder.jp/contests/arc184/tasks/arc184_a 本题为**交互式**问题，且**评测器为自适应（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 翻译