32098번 - Ones 서브태스크점수다국어언어 제한함수 구현

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}, \dots , 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.

Your function guessOnes has the following prototype: std::vector 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}, \dots , p_r$. It works with complexity $O(1)$.

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

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

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

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} ≤ q_{author}$, $score = 1$
• Otherwise $score = 1 - \displaystyle\sqrt[4]{1 - \frac{q_{author}}{q_{participant}}}$

The file Lgrader.cpp is provided on the system, with which you can test your program locally. To do so, you need to add #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.

• Lgrader.cpp ones.h