Last Rook

AtCoder

IDabc269_e

Time2000ms

Memory256MB

Difficulty—

**This is an interactive task** (where your program interacts with the judge's program via input and output). We have an $N$\-by-$N$ chessboard and $N$ rooks. Below, the square at the $i$\-th row from the top and $j$\-th column from the left is denoted by $(i, j)$. Consider placing the rooks on squares of the chessboard. Here, you have to place the rooks so that all of the following conditions are satisfied. * No row contains two or more rooks. * No column contains two or more rooks. Now, $N-1$ rooks are placed on the chessboard so that all of the above conditions are satisfied. You will choose a square that is not occupied by a rook and place a rook on that square. (It can be proved that there is at least one square on which a rook can be placed under the conditions.) However, you cannot directly see which squares of the chessboard are occupied by a rook. Instead, you may ask at most $20$ questions to the judge in the following manner. * You choose integers $A$, $B$, $C$, and $D$ such that $1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$, and ask the number of rooks in the rectangular region formed by the squares $(i, j)$ such that $A \leq i \leq B, C \leq j \leq D$. Find a square to place a rook. ## Constraints * $2 \leq N \leq 10^3$ * $N$ is an integer. ## Input And Output This is an interactive task (where your program interacts with the judge's program via input and output). First, receive the size of the chessboard, $N$, from Standard Input. $N$ Next, repeat asking a question until you find a square to place a rook. A question should be printed to Standard Output in the following format: $?$ $A$ $B$ $C$ $D$ The response will be given from Standard Input in the following format: $T$ Here, $T$ is the response to the question, or `-1` if the question is invalid or more than $20$ questions have been asked. When the judge returns `-1`, the submission is already regarded as incorrect. In this case, terminate the program immediately. When you find a square to place a rook, let $(X, Y)$ be that square and print an answer in the following format. Then, terminate the program immediately. $!$ $X$ $Y$ If there are multiple appropriate answers, any of them will be accepted. [samples] ## Notes * **Each time you print something, end it with a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.** * **If an invalid output is printed during the interaction, the verdict will be indeterminate.** * Terminate the program immediately after printing an answer. Otherwise, the verdict will be indeterminate.

API Response (JSON)

{
  "problem": {
    "name": "Last Rook",
    "description": {
      "content": "**This is an interactive task** (where your program interacts with the judge's program via input and output). We have an $N$\\-by-$N$ chessboard and $N$ rooks. Below, the square at the $i$\\-th row from",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc269_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**This is an interactive task** (where your program interacts with the judge's program via input and output).\nWe have an $N$\\-by-$N$ chessboard and $N$ rooks. Below, the square at the $i$\\-th row from...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments