AT_abc269_e [ABC269E] Last Rook

[problemUrl]: https://atcoder.jp/contests/abc269/tasks/abc269_e **この問題はインタラクティブな問題**（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。 縦横 $ N $ マスのチェス盤と $ N $ 個のルークの駒があります。以下では上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ と表します。 チェス盤のマスにルークを置くことを考えます。ただし、あなたは次の条件をすべて満たすようにルークをチェス盤に置く必要があります。 - 1 つの行に $ 2 $ 個以上のルークが存在しない。 - 1 つの列に $ 2 $ 個以上のルークが存在しない。 今、チェス盤に $ N-1 $ 個のルークが上の条件をすべて満たした状態で置かれています。あなたはルークが置かれていないマスを 1 つ選び、そのマスにルークを置くことにしました。(上の条件をすべて満たすようにルークを置くことができるマスは少なくとも 1 つ以上存在することが証明できます。) ただし、あなたはチェス盤のどのマスにルークが置かれているかを直接知ることはできません。 そのかわりに、ジャッジシステムに対して以下の質問を $ 20 $ 回まで行うことができます。 - 整数 $ A,\ B,\ C,\ D $ を $ 1\ \leq\ A\ \leq\ B\ \leq\ N,\ 1\ \leq\ C\ \leq\ D\ \leq\ N $ を満たすように選ぶ。そして、$ A\ \leq\ i\ \leq\ B,\ C\ \leq\ j\ \leq\ D $ を満たすマス $ (i,\ j) $ からなる長方形領域に置かれているルークの個数を聞く。 ルークを置くことができるマスを見つけてください。 ### Input & Output Format この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。 最初に、チェス盤のサイズ $ N $ を標準入力から受け取ってください。 > $ N $ 次に、ルークを置くことができるマスが見つかるまで質問を繰り返してください。 質問は、以下の形式で標準出力に出力してください。 > $ ? $ $ A $ $ B $ $ C $ $ D $ これに対する応答は、次の形式で標準入力から与えられます。 > $ T $ ここで、$ T $ は質問に対する答えです。ただし、不正な質問を行った、あるいは質問の回数が $ 20 $ 回を超えた場合は $ T $ は `-1` となります。 ジャッジが `-1` を返した場合、提出はすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。 ルークを置くことができるマスを見つけたら、そのマスを $ (X,\ Y) $ として、解答を以下の形式で出力してください。その後、ただちにプログラムを終了してください。 > $ ! $ $ X $ $ Y $ 答えが複数ある場合、どれを出力しても正解とみなされます。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 10^3 $ - $ N $ は整数 ### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。** - **対話の途中で不正な出力を行った場合のジャッジ結果は不定です。** - 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。 ### 入出力例 以下は、$ N=3 $ で $ (1,\ 2),\ (2,\ 1) $ にルークが置かれている場合の入出力例です。 入力 出力 説明 `3` まず整数 $ N $ が与えられます。 `? 1 2 1 3` $ (A,B,C,D)=(1,2,1,3) $ として質問を行います。 `2` 質問の答えは $ 2 $ なので、ジャッジはその値を返します。 `? 2 3 1 1` $ (A,B,C,D)=(2,3,1,1) $ として質問を行います。 `1` 質問の答えは $ 1 $ なので、ジャッジはその値を返します。 `? 1 3 3 3` $ (A,B,C,D)=(1,3,3,3) $ として質問を行います。 `0` 質問の答えは $ 0 $ なので、ジャッジはその値を返します。 `! 3 3` 答えは $ (3,\ 3) $ だとわかったので、それを出力します。