No.3161 Find Presents
Problem Statement
Butsurizuki-kun received many presents for his birthday, but he has lost them somewhere on a 2D plane.
You have a machine that, given a range, determines whether a present exists in that range.
However, running the machine has a cost, so please find all of Butsurizuki-kun's presents within a limited number of uses.
This is an interactive problem (a problem in which your program and the judge system communicate through input and output).
The judge is not adaptive. For each test case, the number and positions of the presents are fixed before your program runs and do not change.
There are $N$ points on a 2D plane, and the coordinates of the $i$-th point are $(X_i, Y_i)$. However, $N, X_i, Y_i$ are not given to you; the judge system keeps these values hidden.
You may ask the judge system the following question up to $8000$ times.
- Choose integers $x_l, x_r, y_l, y_r$ between $0$ and $10^6$, inclusive. They must satisfy $0 \leq x_l \leq x_r \leq 10^6, 0 \leq y_l \leq y_r \leq 10^6$. Then ask whether there exists an integer $i$ between $1$ and $N$, inclusive, such that $x_l \leq X_i \leq x_r$ and $y_l \leq Y_i \leq y_r$.
Determine $N$ and the set $\{ (X_i, Y_i) \}$ using at most $8000$ questions.
Constraints
- $1 \leq N \leq 100$
- $0 \leq X_i, Y_i \leq 10^6$
- $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$
- $N, X_i, Y_i$ are all integers.
Input and Output
This is an interactive problem (a problem in which your program and the judge system communicate through input and output).
Initially, nothing is given as input.
Repeat the following question between $0$ and $8000$ times, inclusive.
For a question, letting the chosen range on the 2D plane be $[x_l, x_r + 1)\times[y_l, y_r + 1)$, print to standard output in the following format, using integers $x_l, x_r, y_l, y_r$ $(0 \leq x_l \leq x_r \leq 10^6, 0 \leq y_l \leq y_r \leq 10^6)$.
? $x_l\ x_r\ y_l\ y_r$
Then, if there exists an integer $i$ between $1$ and $N$, inclusive, such that $x_l \leq X_i \leq x_r$ and $y_l \leq Y_i \leq y_r$, you are given
1
and if no such integer exists, you are given
0
from standard input in the format above.
However, if the question is invalid, -1 is given from standard input.
-1
Specifically, this is given if at least one of the following holds:
- The printed $x_l, x_r, y_l, y_r$ do not satisfy the constraints.
- You asked more than $8000$ questions.
In this case, your answer has already been determined to be incorrect, so terminate your program immediately.
Finally, answer with the number of presents $N$ and the set of positions ${ (X_i, Y_i) }$ by printing $N+1$ lines to standard output in the following format.
! $N$ $X_1\ Y_1$ $X_2\ Y_2$ $\vdots$ $X_N\ Y_N$
More precisely, first print ! and the number of presents $N$ separated by a space on the first line, followed by a newline.
! $N$
Then, on line number $i + 1$ $(1 \leq i \leq N)$, print the position $X_i, Y_i$ of the $i$-th present separated by a space, followed by a newline.
$X_i\ Y_i$
Here, $(X_i, Y_i) \neq (X_j, Y_j)$ must hold for every pair of integers $1 \leq i < j \leq N$.
Your answer is considered correct if ${ (X_i, Y_i) }$ matches the answer as a set, so the order of the presents' positions does not affect the judge result.
After this output, terminate your program immediately.
For all output, your program is also considered incorrect if the output does not follow the specified format. In that case -1 is returned, so terminate your program immediately in that case as well.
Notes
- Each time you print output, end it with a newline and flush standard output. Otherwise, the judge result may be TLE or WA.
- After printing your answer (or receiving
-1), terminate your program immediately. Otherwise, the judge result is undefined. - Note that extra newlines may be treated as output in an invalid format.
- The judge system for this problem is not adaptive. That is, for each test case, the number and positions of the presents are fixed before your program runs and do not change.
Sample Input and Output
In this example, $N=3, { (X_i, Y_i) } = { (1, 1), (2, 2), (5, 5) }$.
| Input | Output | Explanation |
|---|---|---|
? 0 3 0 3 | Asks whether a present exists in the range $ [0, 3+1)\times [0, 3+1)$. | |
1 | Since $(1, 1), (2, 2)$ are in the above range, $1$ is returned as the response. | |
? 3 4 3 4 | Asks whether a present exists in the range $ [3, 4+1)\times [3, 4+1)$. | |
0 | Since no present is in the above range, $0$ is returned as the response. | |
? 1 1 1 1 | Asks whether a present exists in the range $ [1, 1+1)\times [1, 1+1)$. | |
1 | Since $(1, 1)$ is in the above range, $1$ is returned as the response. | |
? 4 5 0 5 | Asks whether a present exists in the range $ [4, 5+1)\times [0, 5+1)$. | |
1 | Since $(5, 5)$ is in the above range, $1$ is returned as the response. | |
! 3 | Outputs the answer that there are $3$ presents. The positions are printed from the next line. | |
5 5 | Answers that there is a present at $(5, 5)$. | |
1 1 | Answers that there is a present at $(1, 1)$. | |
2 2 | Answers that there is a present at $(2, 2)$. | |
| The above questions alone do not determine the number and positions of the presents, but since the judge is not adaptive, this is considered correct. The order of the presents' coordinates does not matter. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
jastaway
butsurizuki