P16387 [IATI 2024] 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},…,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: ```cpp 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: ```cpp 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.

N/A

N/A

### 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}}}$ | **Subtasks** | **Points** | **$k$** | **$q_{author}$** | | :---: | :---: | :---: | :---: | | $1$ | $10$ | $10$ | $14480$ | | $2$ | $10$ | $20$ | $27201$ | | $3$ | $10$ | $50$ | $61908$ | | $4$ | $10$ | $100$ | $114144$ | | $5$ | $10$ | $200$ | $208697$ | | $6$ | $10$ | $500$ | $455937$ | | $7$ | $10$ | $1 000$ | $811792$ | | $8$ | $10$ | $2 000$ | $1422396$ | | $9$ | $10$ | $5 000$ | $2879675$ | | $10$ | $10$ | $10 000$ | $4723779$ |