A Difficult Choice

题目描述

有 $N$ 本书，编号为 $1$ 到 $N$。第 $i$ 本书有一个难度值 $x_i$。这些难度值对你的程序最初是隐藏的，但满足严格递增：

$$x_1 < x_2 < \cdots < x_N .$$

你需要恰好选择 $K$ 本书，使它们的难度和不小于 $A$，且不超过 $2A$。也就是说，需要找到互不相同的下标 $i_1,i_2,\ldots,i_K$，满足：

$$A \le x_{i_1}+x_{i_2}+\cdots+x_{i_K} \le 2A.$$

你最多只能查询 $S$ 本书的难度。若不存在满足条件的选择，你需要报告无解。

本题在 Hydro OJ 中配置为交互/库题。选手程序不直接读入或输出数据，只需要实现指定函数。

实现要求

C++ 选手需要在程序开头包含头文件：

#include "books.h"

你需要实现如下函数：

void solve(int N, int K, long long A, int S);

评测器会对每个测试点调用一次 solve(N, K, A, S)。

在 solve 中，你可以调用以下三个函数。

long long skim(int i)

查询第 $i$ 本书的难度 $x_i$，其中必须满足：

$$1 \le i \le N.$$

该函数返回 $x_i$。

调用 skim 的总次数不能超过 $S$，否则该测试点判为错误。

void answer(std::vector<int> v)

提交一组答案。v 中应当包含恰好 $K$ 个互不相同的下标，且这些书的难度和满足：

$$A \le \sum_{i\in v}x_i \le 2A.$$

调用该函数后，程序会立即结束。

void impossible()

报告不存在满足条件的选择。

调用该函数后，程序会立即结束。

如果存在合法方案，你必须调用 answer；如果不存在合法方案，你必须调用 impossible。

选手程序不要实现 main 函数，也不要向标准输出写入任何额外内容。

样例交互说明

设 $N=15$，$K=3$，$A=42$，$S=8$。

评测器会调用：

solve(15, 3, 42, 8);

一种可能情况是，若调用：

skim(1)

返回 $1337$，则最小的书难度已经很大，显然不可能选出 $3$ 本书使总难度不超过 $84$，因此可以调用：

impossible();

另一种可能情况是：

调用	返回值	说明
skim(1)	$7$	第 $1$ 本书难度为 $7$。
skim(15)	$21$	第 $15$ 本书难度为 $21$。
answer({11, 15, 7})		若对应难度为 $17,21,13$，总和为 $51$，满足 $42\le 51\le 84$。

输入文件说明

本题在 Hydro OJ 中由交互器读取测试数据。每个 .in 文件的格式为评测器内部格式，选手程序不需要直接读取。

数据范围

对于所有测试点：

$$K\le N,$$ $$3\le N,S\le 10^5,$$ $$1\le A,x_i\le 10^{17},$$ $$3\le K\le 10.$$

子任务限制如下：

子任务	分值	限制
1	5	$S=N$，$170\le N\le 10^3$，$K=3$
2	15	$S=N$，$N\ge 170$
3	10	$S\ge 170$，且对所有 $1\le i<N$，$x_{i+1}-x_i\le \frac AK$
4	15	$S\ge 170$，且对所有 $1\le i<N$，$x_{i+1}-x_i\le A$
5		$S\ge 170$
6	20	$S\ge 40$，且对所有 $1\le i<N$，$x_{i+1}-x_i\le A$
7		$S\ge 40$

提交格式示例

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

void solve(int N, int K, long long A, int S) {
    // 在这里实现算法
}

@头文件下发