Secret Sequence

시간 제한1초메모리 제한1024 MB

요약

두 구간의 합을 비교하는 질의를 200번 이하로 사용해, 숨겨진 0과 1 수열에 들어 있는 1의 개수를 구한다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 분할 정복, 구간
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1

입력

예상 출력

예제 2
입력
```
2

0

-1
```
예상 출력
```
? 0 1 1 2

? 0 1 1 1

! 2
```