https://codeforces.com/contest/1520/problem/F1
시간 1초, 메모리 256MB
Interaction
- n t (1 ≤ n ≤ 2⋅105, t=1).
- k (1 ≤ k ≤ n).
It is guaranteed that at the moment of the request the array contains at least k zeros.
입력된 배열에는 최소 k개의 0이 존재합니다.
After that, you can make no more than 20 requests.
그 이후 20번으 질문을 할 수 있습니다.
? l r — find out the sum of all elements in positions from l to r (1≤l≤r≤n) inclusive.
(? l r)의 형태로 l ~ r 까지의 원소의 합을 리턴 받습니다.
Use the following format to output the answer (it is not a request, it doesn't count in 20):
! x — position of the k-th zero.
아래의 형태로 정답을 출력합니다.
(! x)
조건
-
Positions in the array are numbered from left to right from 1 to n inclusive.
배열의 위치는 1 ~ n까지입니다. -
To flush the output buffer, you need to do the following immediately after the query output and the end-of-line character:
buffer를 비우기 위해 ?하면서 질문을 한 이후에 입력을 받은 후 buffer를 비워야 합ㄴ디ㅏ.
interactive형태의 문제 자체가 익숙하지 않아 생소했다.
일단 정답이 되는 배열은 가려져 잇는 상태고 우리가 질문을 해서 찾아야 한다.
어떻게 질문을 하면 될까??
0의 개수
1에서 부터 내가 원하는 위치까지의 0의 개수를 계속 알 수 있다면 k - 1 -> k개가 되는 순간을 찾을 수 있을 것이다.
이거를 어떻게 찾아야 할까??
이분탐색
계속 (? 1 x)의 형태로 질문을 한 다면 알 수 있다. 그리고
x는 mid라서 left와 right의 형태는 언제나와 동일한 조건을 사용하자.
import sys
n, t = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())
left, right = 1, n
while left <= right:
mid = (left + right) // 2
print(f"? {1} {mid}")
sys.stdout.flush()
total = mid - int(sys.stdin.readline())
if total >= k:
right = mid - 1
else:
left = mid + 1
print(f"! {left}")
