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 $ 枚が偽物です。 鑑定士は $ 1 $ 度の鑑定で $ 2 $ つの硬貨が同種か異種かを判定できます。厳密には、 - $ 2 $ つの硬貨が「双方とも本物」「双方とも偽物」のどちらかであれば、同種と判定する。 - そうでないとき、異種と判定する。 $ Q $ 回以下の鑑定で、全ての偽物の硬貨を特定してください。 ### Input & Output Format この問題はインタラクティブな問題です。 最初に、 $ N,M,Q $ を標準入力から受け取ってください。 > $ N $ $ M $ $ Q $ 次に、以下の流れで鑑定を $ 0 $ 回以上 $ Q $ 回以下行ってください。 まず、次の形式で標準出力に出力することで、硬貨 $ x,y $ を鑑定することを表します。 (末尾に改行を入れること。) > ? $ x $ $ y $ ここで、 $ x,y $ は $ 1 $ 以上 $ N $ 以下の相異なる整数である必要があります。 これに対するジャッジシステムの応答は、以下の $ 3 $ 通りです。 ``` 0 ``` 応答が `0` であるとき、硬貨 $ x,y $ が同種であることを表します。 ``` 1 ``` 応答が `1` であるとき、硬貨 $ x,y $ が異種であることを表します。 ``` -1 ``` 応答が `-1` であるとき、不当な鑑定であることを表します。具体的には - 出力した $ x,y $ が制約を満たさなかった - $ Q $ 回を超えて鑑定が行われた の少なくともひとつが満たされた際にこの応答を行います。 この応答を受け取った場合、プログラムはすでに不正解とみなされています。直ちにプログラムを終了してください。 最後に、次の形式で標準出力に出力することで、硬貨 $ A_1,A_2,\dots,A_{M} $ が偽物であると解答します。 (末尾に改行を入れること。) > ! $ A_1 $ $ A_2 $ $ \dots $ $ A_{M} $ ここで、 $ A_i $ は $ 1 $ 以上 $ N $ 以下の相異なる整数である必要があります。 この出力の後、直ちにプログラムを終了してください。 なお、全ての出力について、出力が指定された形式を満たさなかった場合もプログラムが不正解とみなされます。 その後 `-1` が返答されるので、その場合も直ちにプログラムを終了してください。

N/A

N/A

### 制約 - $ \color{red}{N\ =\ 1000} $ - $ \color{red}{M\ =\ 10} $ - $ \color{red}{Q\ =\ 950} $ ### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。** そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。 - 解答を出力したら (または `-1` を受け取ったら) ただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。 - 余計な改行は不正なフォーマットの出力とみなされることに注意してください。 - **この問題のジャッジシステムは、適応的(adaptive)です。** つまり、ジャッジシステムは、任意のタイミングにおいて、整合性がとれる限り、偽物の硬貨として想定しているものを変更する可能性があります。詳しくは入出力例も参照してください。 ### 入出力例 この入力では $ N=5,M=2,Q=10 $ であり、ジャッジシステムは最初硬貨 $ 1,2 $ が偽物であると想定しています。 なお、この例は制約を満たさないので、ジャッジには含まれないことに注意してください。 入力出力説明`5 2 10`$ N,M,Q $ が与えられます。`? 1 2`硬貨 $ 1,2 $ について鑑定を行います。`0`硬貨 $ 1,2 $ は同種だと判定します。`? 1 3`硬貨 $ 1,3 $ について鑑定を行います。`1`硬貨 $ 1,3 $ は異種だと判定します。`? 1 4`硬貨 $ 1,4 $ について鑑定を行います。`1`硬貨 $ 1,4 $ は異種だと判定します。`! 1 2`硬貨 $ 1,2 $ が偽物だと解答します。確かに硬貨 $ 1,2 $ は偽物だと想定されていますが、硬貨 $ 3,4 $ を偽物であると想定しても整合性が取れます。 よって、ジャッジシステムは偽物の硬貨として想定しているものを硬貨 $ 3,4 $ に変更できます。 これにより、ジャッジシステムは不正解の判定を下すこともあります。