| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 2048 MB | 13 | 0 | 0 | 0.000% |
This is an interactive problem.
Busy Beaver has a secret array $a_1,a_2,\dots,a_N$ of distinct positive integers between 1ドル$ and 10ドル^9$. For 1ドル \le l \le r \le N,ドル Busy Beaver defines $f(l,r)$ to be equal to $\min(a_l,a_{l+1},\dots,a_r)$.
Busy Beaver allows you to ask some queries to uncover information about the array. In a query, you can specify $l$ and $r$ (1ドル \le l \le r \le N$), and Busy Beaver will tell you the value of $f(l,r)$ for a cost of $\frac{1}{r-l+1}$. You must ensure that the total cost of all queries is at most 1ドル$.
After making all your queries, you report to Busy Beaver a list of pairs $(l,r)$ for which you determined the value of $f(l,r)$. If any of your answers are wrong, Busy Beaver will be displeased and award you 0ドル$ points. Otherwise, your score will depend on the fraction of the $\frac{N(N+1)}{2}$ pairs $(l,r)$ with 1ドル \le l \le r \le N$ where you determined a value for $f(l,r)$ (see the Scoring section for more details).
To reduce the size of the output, you report your knowledge using $k$ tuples of the form $(l_{min},l_{max},r_{min},r_{max},v),ドル where 1ドル \le l_{min} \le l_{max} \le r_{min} \le r_{max} \le N$ and 1ドル \le v \le 10^9$. Each tuple declares that $f(l,r) = v$ for all $l_{min} \le l \le l_{max}$ and $r_{min} \le r \le r_{max}$. Any pairs $(l,r)$ that do not correspond to any tuple are treated as unspecified. It is allowed to have multiple tuples that describe the same pair $(l,r),ドル but you will receive 0ドル$ points if these tuples indicate inconsistent values.
The first line of input contains a single integer $N$ (1ドル \le N \le 10^5$), the length of Busy Beaver's secret array.
You may repeatedly ask queries by outputting a line of the form "? $l$ $r$", where 1ドル \le l \le r \le N$. Then, the judge will respond with a single integer, denoting the value of $f(l,r)$. If you exceed a total cost of 1ドル,ドル the judge will instead respond with $-1,ドル and you should terminate your program immediately to receive a Wrong Answer verdict.
After you are finished with your queries, first output a line of the form "! $k$" (0ドル \le k \le 2N$), representing that you will describe your knowledge of $f$ using $k$ tuples $(l_{min},l_{max},r_{min},r_{max},v)$.
Then, the next $k$ lines should each contain 5ドル$ space-separated integers $l_{min},ドル $l_{max},ドル $r_{min},ドル $r_{max},ドル and $v,ドル specifying a tuple.
The interactor is not adaptive, meaning that Busy Beaver will not change the entries of his secret array $a$ in response to your queries.
For all test cases used for scoring, $N = 10^5$.
If you exceed a cost of 1ドル$ or any of the values you claim for $f(l,r)$ are incorrect, you will receive 0ドル$ points and a Wrong Answer verdict.
Otherwise, let $x$ be the fraction of the $\frac{N(N+1)}{2}$ values of $f(l,r)$ that you specified a value for. Your score for the test case will be equal to $$ \left\lfloor \min\left(100,100 \cdot \frac{x}{0.8}\right) \right\rfloor. $$ In particular, if $x \ge 0.8,ドル then you will receive full points for the test case.
Your final score will be the minimum score over all test cases.
6 31 26 53
? 1 3 ? 1 6 ? 5 6 ! 4 1 1 3 3 31 1 4 4 6 26 2 3 5 5 26 5 5 6 6 53
Note that the sample does not satisfy $N = 10^5,ドル so it will not be included in the actual test cases. It is provided only to illustrate the interaction format.
In the sample, Busy Beaver's secret array is $a = [31,41,59,26,53,58]$. You decide to make the following queries:
Note that the total cost of all your queries is $\frac13+\frac16+\frac12 = 1,ドル which does not exceed 1ドル$ as required.
From this information, you report to Busy Beaver the following values of $f(l,r)$ you have deduced:
After removing overlaps, you reported 14ドル$ of the values of $f(l,r)$ out of the $\frac{N(N+1)}{2} = 21$ distinct pairs $(l,r)$. Therefore, Busy Beaver will calculate $x = \frac{14}{21}$ and give you a score of $$ \left\lfloor 100 \cdot \frac{14/21}{0.8} \right\rfloor = \left\lfloor 83.\bar{3} \right\rfloor = 83 $$ for this interaction.