| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 129 | 14 | 14 | 13.333% |
There is a secret sequence of zeros and ones of length $n,ドル and you want to know the number of ones in the sequence. You are allowed to ask queries by giving four integers 0ドル \leq a \leq b \leq c \leq d \leq n$. The answer to the query will be $-1$ if the sum of the numbers at positions $a, a+1, ..., b-1$ is larger than the sum of the numbers at positions $c, c+1, ..., d-1,ドル and 1ドル$ if the sum is smaller. If the sums are equal, the answer will be 0ドル$.
The indices of the sequence start at 0ドル$ and end at $n-1$. Note that the intervals you're querying can be empty, if $a = b$ or $c = d$ respectively. The sum of the numbers in an empty interval is 0ドル$.
Figure out the total number of ones in the sequence using at most 200ドル$ queries.
This problem is interactive.
Your program should start by reading an integer $n,ドル the length of the sequence (1ドル \le n \le 2 \cdot 10^5$).
Then for each query you make, you should print a single line containing a question mark (?) and four integers 0ドル \leq a \leq b \leq c \leq d \leq n,ドル separated by spaces. The grader will then read these numbers and in return print a line with either $-1,ドル 0ドル$ or, 1ドル,ドル which can be read by your program.
Your program should then repeat this until you want to guess how many ones there are, which you do by printing a line containing an exclamation mark (!) followed by a single integer number $x,ドル separated by a space. After you print this line, your program should terminate. If the number $x$ is correct, i.e. if it equals the number of ones in the sequence, you pass the test case.
You must make sure to flush standard output before reading the grader's response, or else your program will get judged as Time Limit Exceeded. This works as follows in various languages:
System.out.println() flushes automatically.print() flushes automatically.cout << endl; flushes, in addition to writing a newline. If using printf, fflush(stdout).The grader is not adaptive. That is, the numbers in the sequence are fixed for each test case and will not vary depending on your queries.
You can make at most 200ドル$ ? queries.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | There are either no ones or a single one. |
| 2 | 5 | $n \leq 200$ |
| 3 | 15 | The ones form a contiguous segment. |
| 4 | 20 | $n \leq 4000$ |
| 5 | 15 | No constraints. |
5 1 -1 0
? 0 1 4 5 ? 1 3 4 5 ? 0 1 3 4 ! 3
The secret sequence in this sample is 01101ドル,ドル so $n = 5,ドル which is what the judge writes on the first line. The program then asks which number is greater: the first (at position 0ドル$) or the last (at position 4ドル$). The judge answers that the last number is greater, so we then know it has to be a one while the first number is a zero. After this, the program asks which is greater: the sum of the numbers at position 1ドル$ and 2ドル$ or the number at position 4ドル$. The judge answers that the sum of the two numbers at position 1ドル$ and 2ドル$ is greater, and since we already know that there is a one at position 4ドル,ドル this means both the numbers at position 1ドル$ and 2ドル$ are ones. Finally, the program asks which is greater: the number at position 0ドル$ or the number at position 3ドル$. The judge answers that they are the same, and so since the number at position 0ドル$ is zero, which we know from the first query, this is also the case for the number at position 3ドル$.
Hence there are 3ドル$ ones in total, so the program answers this.
2 0 -1
? 0 1 1 2 ? 0 1 1 1 ! 2
Contest > Swedish Coding Cup > Swedish Coding Cup Finals 2021 D번