Table of Contents

ExplanationImplementation

Official Editorial (C++)

Explanation

We use binary search to find the location of the kkth zero.

To do this, we set a midpoint and then check if the number of zeros in the left half is greater than or equal to or strictly less than kk. This allows us to narrow the location of the kkth zero to either the left or right half.

Implementation

Time Complexity: O(log⁡N)\mathcal{O}(\log N)

C++

#include <bits/stdc++.h>
using namespace std;


int query(int r, int k) {
	int res;
	cout << "? " << 1 << " " << r << '\n';
	cin >> res;
	return r - res <= k;
}

Java

import java.io.*;
import java.util.*;


public class GuessTheKthZero {
	public static void main(String[] args) {
		Kattio io = new Kattio();


		int n = io.nextInt();
		int t = io.nextInt();
		int k = io.nextInt() - 1;

Python

def query(r: int, k: int) -> bool:
	print(f"? 1 {r}")
	res = int(input())
	return r - res <= k




n, t = map(int, input().split())
k = int(input()) - 1


lo = 0

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum