Problem Description

Radko again wants to know Marti’s sequence $p_1,p_2,\dots,p_n$. This time, Marti decided to be more helpful and directly say that the sequence consists of $n$ bits of $0$ and $1$, exactly $k$ of which are $1$. This time he will only answer the following question:

• “Is there a $1$ among $p_l,p_{l+1},…,p_r$?”

Unfortunately, Radko is still too busy and again outsources the task to you. Your program will be tested on $n_{tests}$ subtests for each test, and your score will be calculated based on the total number of questions you use to find the respective sequences.

Implementation details

Your function $\verb|guessOnes|$ has the following prototype:

std::vector<int> guessOnes(int n, int k);

It will be called $n_{tests}$ times for each test and will receive as arguments the sequence length $n$ and the number of ones $k$. The function should return a vector of $k$ numbers - the positions of the ones in ascending order.

The jury’s function $hasOnes$ has the following prototype:

bool hasOnes(int l, int r);

Your program can call it as many times as it wants. It receives two indexes $l$ and $r$ from $1$ to $n$ for which you want to ask a question. The function returns whether there is a $1$ among $p_l,p_{l+1},…,p_r$. It works with complexity $O(1)$.

Your program must implement the function $\verb|guessOnes|$, but should not contain a function $\verb|main|$. Also, it must not read from the standard input or print to the standard output. Your program must also include the header file $\verb|ones.h|$ by an instruction to the preprocessor: $\verb|#include "ones.h"|$

As long as it respects these conditions, your program can contain any helper functions, variables, constants, and so on.

Local testing

The file $\verb|Lgrader.cpp|$ is provided on the system, with which you can test your program locally. To do so, you need to add $\verb|#include "Lgrader.cpp"|$ to your code.

The first line of the standard input contains the numbers $n$, $k$ and $n_{tests}$.

The next $n_{tests}$ lines contain $k$ numbers each – the positions of the ones. If your program successfully finds the correct sequence for each test, it will output the total number of questions you used for all sequences.

Hint

Constraints

• Every sequence is uniform random generated.
• $n = 100 000$
• $n_{tests} = 100$

Subtasks and scoring

The fraction of points you will get on a subtask depends on the total number of questions you ask on a subtest, $q_{participant}$, and the subtask constant $q_{author}$.

If $q_{participant} \leq q_{author}$, $score = 1$

Otherwise $score = 1 - \sqrt[4]{1 - \frac{q_{author}}{q_{participant}}}$