P8122 [BalticOI 2021] A Difficulty Choice (Day1)

**This is an interactive problem.** Thanks to the provider of the interactive library and checker, [Hi_chocolate](https://www.luogu.com.cn/user/193198), for the great contribution to this problem. ### Special Notes **Notes for submitting this problem on Luogu (if anything differs from the original statement, please follow this section):** 1. When submitting, please add the following function declarations in your program: ```cpp extern "C" long long skim (int i); extern "C" void answer (std::vector v); extern "C" void impossible (); ``` The `solve` function you implement should be: ```cpp extern "C" void solve (int N, int K, long long A, int S); ``` 2. At the beginning of the program, you do not need to, and should not, include the `books.h` header file. 3. Only `C++` (`C++`, `C++11`, `C++14`, `C++17`) submissions are supported.

You are determined to get accepted on BalticOI, and the way to do that is studying. You walk into a bookstore. There are $N$ books on the shelf, numbered from $1$ to $N$. The difficulty of the $i$-th book is $x_i$. You want to choose $K$ books out of these $N$ books for studying. You do not want the material to be too easy or too hard, so you want to ensure that the sum of difficulties of these $K$ books lies in the interval $[A,2A]$. Unfortunately, you do not know the exact values of $x_i$, so you need to skim the books to learn their difficulties. The shop owner is a neat freak and does not want you to skim too many books, so you are allowed to skim at most $S$ books and then decide. Luckily, you are told that as the book index increases, the difficulty is strictly increasing. Please write a program that, by skimming books, buys the books you need, or reports that it is impossible. ### Interaction Format This is an interactive problem. You need to write the function `void solve (int N, int K, long long A, int S)`. $N,K,A,S$ are defined above, and it is guaranteed that $x_1

See “Interaction Format”.

See “Interaction Format”.

#### Sample 1 Explanation $N=15$, $K=3$, $A=42$, $S=8$. Below are two possible sequences of calls that would be accepted: Example 1: |Your program|Return value| |:-:|:-:| |`skim(1)`|$1337$| |`impossible`|-| Example 2: |Your program|Return value| |:-:|:-:| |`skim(1)`|$7$| |`skim(15)`|$21$| |`answer({11,15,7})`|-| #### Constraints and Assumptions **This problem uses bundled testdata.** - Subtask 1 (5 pts): $S=N$, $170 \le N \le 1000$, $K=3$. - Subtask 2 (15 pts): $S=N$, $N \ge 170$. - Subtask 3 (10 pts): $S \ge 170$, $x_{i+1}-x_i \le \frac A K$. - Subtask 4 (15 pts): $S \ge 170$, $x_{i+1}-x_i \le A$. - Subtask 5 (15 pts): $S \ge 170$. - Subtask 6 (20 pts): $S \ge 40$, $x_{i+1}-x_i \le A$. - Subtask 7 (20 pts): $S \ge 40$. For $100\%$ of the testdata, $K \le N$, $3 \le N,S \le 10^5$, $1 \le A,x_i \le 10^{17}$, $3 \le K \le 10$. #### Note Translated from [BalticOI 2021 Day1 A A Difficulty Choice](https://boi.cses.fi/files/boi2021_day1.pdf). Translated by ChatGPT 5