题目描述

题目译自 BalticOI 2021 Day1「A Difficult Choice」，译者 cnyz。

有一个长度为 $N$ 的未知的单调上升整数序列 $x$，您需要选出这个序列中的 $K$ 个数，使得他们的和 $\ge A$ 且 $\le 2\times A$。

您最多可以得知 $S$ 个 $x$ 中的元素。

试选出这个序列满足要求的 $K$ 个数。

实现细节

如果您是 C++ 选手，您需要声明 books.h。

您需要实现一个函数 void solve(int N,int K,long long A,int S)，这个函数可以调用如下三个函数（如下均为样例交互库情况）：

• long long skim(int i)
  • 这个函数将返回 $x_i$ 的值
  • 这个函数至多能被调用 $S$ 次，否则您的程序会被判为 Out of books to skim.。
  • 您需要保证 $1\le i\le N$，否则您的程序会被判为 Invalid skim.。
• void answer(vector<int> v)
  • 如果有解，返回存储在 vector<int> v 中的解。
  • 您需要保证 $1\le v_i\le N$ 且 $\forall i\not=j,v_i\not=v_j$，否则您的程序会被判为 Invalid answer。
  • 您需要保证 $x_{v_i}$ 的和 $\ge A$ 且 $\le 2\times A$，否则您的程序会被判为 Wrong answer。
  • 如果您上述条件都满足了，您的程序会被判为 Correct: s book(s) skimmed. ，其中 $s$ 为 skim 函数的调用次数。
• void impossible()：如果无解，返回无解。
  • 如果您调用了这个函数，您的程序会被判为 Impossible (not checked): s book(s) skimmed.，，其中 $s$ 为 skim 函数的调用次数，注意这并不意味您的程序是对的。

评测用的交互库仅会返回 Not Correct 或者 Correct。

输入格式

样例交互库从标准输入流读入以下数据：

第一行，四个整数 $N$，$K$，$A$，$S$。 第二行，$N$ 个整数 $x_i$，注意序列 $x$ 单调上升。

如果输入不符格式，则直接判为 Invalid input.。

输出格式

样例交互库向标准输入流输出以下数据：

仅一行表示您的状态。

样例交互

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

首先我们调用 solve(15, 3, 42, 8)。

那么，样例交互可能会是这样的：

数据范围及限制

对于所有数据，满足 $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$，$\forall 1\le i <N,x_{i+1}-x_i\le \frac{A}{K}$。
• 子任务 $4$（$15$ 分）：$S\ge 170$，$\forall 1\le i <N,x_{i+1}-x_i\le A$。
• 子任务 $5$（$15$ 分）：$S\ge 170$。
• 子任务 $6$（$20$ 分）：$S\ge 40$，$\forall 1\le i <N,x_{i+1}-x_i\le A$。
• 子任务 $7$（$20$ 分）：$S\ge 40$。