IATI | biggest

Two players, $A$ and $B$, play the following game. $A$ comes up with a permutation $p_1, p_2, ..., p_N$ of the integers $1, 2, ..., N$, which $B$ does not know. $B$ can ask questions of the type "Which of $p_x$ and $p_y$ is greater?" for any numbers $x$ and $y$, such that $1 \leq x, y \leq N$. $B$ wants to find the indices in the permutation of the $K$ largest numbers (i.e. the numbers $N, N−1, ..., N - K + 1$) using the smallest possible count of queries, given that the first $N - 1$ queries are not counted towards the total number of queries. The jury program will play the role of $A$, and yours of $B$.

Task

Write a function which will be compiled with the jury's program and, by asking questions, will try to find the indices in the permutation of the $K$ largest numbers with the smallest possible count of queries. Note that the first $N - 1$ queries are not counted towards the total number of queries.

Implementation details

Your function biggest should have the following format:

std::vector<int> biggest (int N, int K);

It is called once by the jury program with the following parameters:

• $N$ - count of the integers in the permutation;
• $K$ - count of the required largest values.

The function must return a vector that contains the indices in the permutation of the $K$ largest numbers, and they must be arranged from the index of $N$ to the index of $N - K + 1$.

You are provided with a function to communicate with the jury program

int compare (int x, int y);

where $x$ and $y$ are integers for which $1 \leq x, y \leq N$. The function returns $x$, if $p_x > p_y$, and $y$ otherwise.

Your program can call this function an unlimited number of times, but if it is called more than 3 000 000 times, you will get 0 points for the corresponding test.

Your code must contain the function biggest. It may also contain other code and functions necessary for your work, but it must not contain the main function main. At the beginning, your file must contain: #include "biggest.h".

Local testing

You have been provided with the files biggest.h and Lgrader.cpp, which you can compile with your program to test on your local computer.

When testing, $N, K$ and test type must be entered. If the type is 0, the permutation is entered; otherwise a seed must be entered to generate the permutation. If you want to configure it in another way, you can make any changes you want to the files provided to you.

Constraints

• $N = 100\ 000$ in all tests
• $1\ \leq \ K\ \leq \ 100\ 000$
• The permutation $p$ in any test is randomly generated, so that any permutation has an equal chance to be present.

Scoring

Each test is scored separately.

For a given test, your solution will receive points other than 0 if the function biggest successfully finishes execution with no more than 3 000 000 calls to the compare function and returns a vector of length $K$ that contains the correct indices of the required largest values. The points you will receive for the test are equal to the maximum number of points for the test, multiplied by:

$\min\left( 1,\frac{authorScore + 1}{yourScore + 1} \right)$

Here $\text{yourScore}$ is the count of the queries that your solution uses after the first $N−1$ queries, and $\text{authorScore}$ is the count of the queries that the author's solution uses.

The tests are distributed as follows

Example

Explanation

The permutation is [4, 1, 3, 2]. The contestant's program used a total of 5 queries. If the author's program has used 4 queries, this test will receive 2/3 of the test's score. More precisely, here $yourScore = 5 - (4 - 1) = 2$, $authorScore = 4 - (4 - 1) = 1$ and that is how we calculate the ratio $\frac{authorScore + 1}{yourScore + 1} = \frac{1 + 1}{2 + 1} = \frac{2}{3}$.