21845번 - A Difficult(y) Choice 서브태스크다국어언어 제한함수 구현

Immortal glory goes to those who win a medal at BOI. As you are keen on being one of them, this is your way to go^*: training, training, training!

As a first step in your training program, you decided to buy some computer science books. Luckily, your local book store has a special offer with a hefty discount when you buy exactly $K$ books.

Now you are to select the $K$ books to buy from the set of $N$ computer science books (numbered 1 to $N$) offered in the book store. Your key selection factor is difficulty: Each book $i$ has an individual (and fully objective) difficulty $x_i$, and the total difficulty of a set of books is the sum of their individual difficulties. You don’t want the selected books to be too easy (then you wouldn’t learn enough to win that precious medal) or too difficult (then you wouldn’t understand them before the contest starts). To be precise, you want the total difficulty of the selected books to be at least $A$, but not more than $2A$.

Judging the actual difficulty of a book requires you to skim through it, but the store owner won’t be happy if you read many books without buying them. She allows you to skim through at most $S$ books. Fortunately, she also tells you that the books are sorted by increasing difficulty.

Write a program that assists you in deciding on which books to skim through, and in the end tells you which books to buy.

^* “Is it, really?,” says a tiny voice in your head…

This is a communication task. You must implement the function void solve(int N, int K, long long A, int S) where $N$, $K$, $A$ and $S$ are as described above. The individual difficulties $x_1 < x_2 < \cdots < X_N$ are initially kept hidden from your program. For each testcase, this function is called exactly once. In the function, you can use the following other functions provided by the grader:

• long long skim(int i) skims through the $i$-th book and returns its difficulty $x_i$ ($1 \le i \le N$).
• void answer(vector v) buys your selection of books. This function has to be called with $v = \{i_1, \dots, i_K\}$ ($1 \le i_1, \cdots , i_K \le N$) where the $i_j$’s are pairwise distinct and satisfy $A \le x_{i_1} + \cdots + x_{i_K} \le 2A$.
• void impossible() states that it is impossible to buy a set of $K$ books with the desired difficulty.

If there exists a selection of $K$ books with the desired difficulty, you must call answer exactly once. Otherwise, you must call impossible exactly once. Your program will be automatically terminated after a call to one of these two functions.

If any of your function calls does not match the above format, or if you call skim more than $S$ times, your program will be immediately terminated and judged as Not correct for the respective testcase.

If you use C++, you must include the file books.h in your source code. To test your program locally, you can link your program with sample_grader.cpp which can be found in the attachment for this task in CMS (see below for a description of the sample grader). The attachment also contains a sample implementation with additional explanations as books_sample.cpp.

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

Consider a testcase with $N = 15$, $K = 3$, $A = 42$, and $S = 8$. At the beginning, the grader calls your function solve as solve(15, 3, 42, 8). Then, two possible interactions between your program and the grader could look as follows:

The sample grader expects on standard input two lines. The first line should contain the four integers $N$, $K$, $A$ and $S$. The second line should contain a list of 𝑁 integers, the sequence of difficulties $x_1, x_2, \dots, x_N$ which has to be strictly increasing. Then, the grader writes to standard output a protocol of all grader functions called by your program. At the end, the grader writes one of the following messages to standard output:

• Invalid input. The input to the grader via standard input was not of the above format.
• Invalid skim. The function skim was called with invalid parameters.
• Out of books to skim. The function skim was called more than $S$ times.
• Invalid answer. The function answer was called with invalid parameters.
• Wrong answer. The function answer was called with a wrong selection of books.
• No answer. The function solve terminated without calling answer or impossible.
• Impossible (not checked): s book(s) skimmed. None of the above cases occurred, the function skim was called 𝑠 times and the function impossible was called. It is not checked wether this is the correct answer.
• Correct: s book(s) skimmed. None of the above cases occurred and the function skim was called $s$ times.

In contrast, the grader which is used for the evaluation of your submission will only output Not correct (for any of the above errors) or Correct. Both the sample grader and the grader used for evaluation will terminate your program automatically whenever one of the above errors occurs or if your program calls answer or impossible.

• books.h
• sample_grader.cpp