P16387 [IATI 2024] Ones

Radko 又想打听 Marti 的序列 $p_1,p_2,\dots,p_n$ 了。这一次，Marti 决定更友善一些，直接告诉他这个序列由 $n$ 个 $0$ 和 $1$ 组成，并且其中恰好有 $k$ 个 $1$。这一次，他只会回答以下问题： - “在 $p_l,p_{l+1},…,p_r$ 中是否存在一个 $1$？” 遗憾的是，Radko 仍然忙得不可开交，于是再次将任务外包给了你。你的程序在每个测试点中会接受 $n_{tests}$ 个子测试的检验，而你的得分将根据你为找出相应序列所提出的问题总数来计算。 ### 实现细节 你需要实现的函数 $\verb|guessOnes|$ 具有如下原型： ```cpp std::vector guessOnes(int n, int k); ``` 该函数在每个测试点中会被调用 $n_{tests}$ 次，并接收参数：序列长度 $n$ 以及 $1$ 的个数 $k$。函数应返回一个包含 $k$ 个数的向量——以升序排列的各个 $1$ 所在的位置。 裁判函数 $hasOnes$ 具有如下原型： ```cpp bool hasOnes(int l, int r); ``` 你的程序可以随意调用该函数任意多次。它接收两个下标 $l$ 和 $r$（取值范围为 $1$ 到 $n$），表示你想要询问的区间。该函数返回在 $p_l,p_{l+1},…,p_r$ 中是否存在 $1$。它的时间复杂度为 $O(1)$。 你的程序必须实现函数 $\verb|guessOnes|$，但不应包含 $\verb|main|$ 函数。同时，它不得从标准输入读取数据或向标准输出打印内容。你的程序还必须通过预处理器指令包含头文件 $\verb|ones.h|$：$\verb|#include "ones.h"|$ 只要遵守这些条件，你的程序可以包含任意辅助函数、变量、常量等。 ### 本地测试 系统提供了文件 $\verb|Lgrader.cpp|$，你可以凭借它在本地测试你的程序。为此，你需要在你的代码中添加 $\verb|#include "Lgrader.cpp"|$。 标准输入的第一行包含数字 $n$、$k$ 和 $n_{tests}$。 接下来的 $n_{tests}$ 行，每行包含 $k$ 个数字——即各个 $1$ 的位置。如果你的程序成功为每个子测试找到了正确的序列，它将会输出你为所有序列所提出的问题总数。

无

无

### 数据范围 - 每个序列均为均匀随机生成。 - $n = 100\,000$ - $n_{tests} = 100$ ### 子任务与评分 你在一个子任务上获得的分数比例取决于你在一个子测试中提出的问题总数 $q_{participant}$，以及该子任务的常数 $q_{author}$。 若 $q_{participant} \leq q_{author}$，则 $score = 1$ 否则 $score = 1 - \sqrt[4]{1 - \frac{q_{author}}{q_{participant}}}$ | **子任务** | **分数** | **$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$ | 翻译由 DeepSeek V4 Pro 完成