Ones

Time limit1sMemory limit1024 MB

Summary

Find the positions of all k ones in a random n-bit sequence using range queries that only ask whether a segment contains a 1, minimizing the query count.

Level: Medium6 of 10
Topics: Binary search, Probability, Implementation
Solved: No attempts yet

Problem

Radko again wants to learn Marti's sequence $p_1, p_2, \dots, p_n$ . This time Marti decided to be more helpful and says directly that the sequence has $n$ bits, each 0 or 1, and exactly $k$ of them are 1. He will again answer only this question:

Is there a 1 among $p_l, p_{l+1}, \dots, p_r$ ?

Unfortunately, Radko is still too busy and hands the task to you again. Your program is tested on $n_{tests}$ subtests per test, and your score is the total number of questions you use to find each sequence.

Constraints

Every sequence is generated uniformly at random.
$n = 100000$
$n_{tests} = 100$

Examples1

Example 1
Input
```
1 0
```
Expected output
```
! 0
```