题目描述

Radko 又想知道 Marti 的序列 p_1, p_2, ..., p_n。

这一次，Marti 更“友好”了一些，直接告诉他：

• 这个序列只由 0 和 1 组成；
• 其中恰好有 k 个位置上的值为 1。

此外，Marti 只会回答如下类型的问题：

• “在 p_l, p_{l+1}, ..., p_r 中，是否至少存在一个 1？”

可惜 Radko 仍然很忙，于是再次把任务外包给你。

在每个测试中，评测机会对你的程序进行 ntests 次测试。你的得分将取决于：为了找出这些序列，你一共使用了多少次询问。

实现要求

你需要实现如下函数：

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

该函数在每个测试中会被调用 ntests 次，并接收两个参数：

• n：序列长度；
• k：序列中 1 的个数。

函数需要返回一个长度为 k 的数组，表示所有值为 1 的位置，且这些位置必须按升序排列。

评测器提供如下函数：

bool hasOnes(int l, int r);

你的程序可以任意多次调用它。它接收两个下标 l, r（满足 1 <= l <= r <= n），并返回区间 p_l, p_{l+1}, ..., p_r 中是否存在至少一个 1。

该函数的时间复杂度为 O(1)。

代码要求

你的程序必须：

• 实现 guessOnes；
• 不能包含 main 函数；
• 不能从标准输入读取，也不能向标准输出打印；
• 必须包含头文件：

#include "ones.h"

在满足这些条件的前提下，你可以自由定义辅助函数、变量、常量等。

约束条件

• 每个序列都是均匀随机生成的；
• n = 100000；
• ntests = 100。

子任务与评分

你在某个子任务上的得分比例，取决于你在一个子测试中使用的总询问次数 q_participant，以及该子任务给定的常数 q_author。

• 如果 q_participant <= q_author，则 score = 1；
• 否则：

score = 1 - sqrt(1 - q_author / q_participant)

子任务表

本地评测

系统提供文件 Lgrader.cpp，你可以将其与你的代码一起编译来进行本地测试。

使用方法：在你的代码中加入

#include "Lgrader.cpp"

本地评测器输入格式

• 第 1 行：三个整数 n, k, ntests；
• 接下来 ntests 行：每行包含 k 个整数，表示该组测试中所有 1 的位置。

如果你的程序成功找出每一组测试的正确序列，本地评测器会输出你对所有序列总共使用的询问次数。