biggest

Time limit: 0.3s Memory limit: 256MB Input: Output:

Two players, AA and BB, play the following game. AA comes up with a permutation p1,p2,...,pNp_1, p_2, ..., p_N of the integers 1,2,...,N1, 2, ..., N, which BB does not know. BB can ask questions of the type "Which of pxp_x and pyp_y is greater?" for any numbers xx and yy, such that 1x,yN1 \leq x, y \leq N. BB wants to find the indices in the permutation of the KK largest numbers (i.e. the numbers N,N1,...,NK+1N, N−1, ..., N - K + 1) using the smallest possible count of queries, given that the first N1N - 1 queries are not counted towards the total number of queries. The jury program will play the role of AA, and yours of BB.

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 KK largest numbers with the smallest possible count of queries. Note that the first N1N - 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:

  • NN - count of the integers in the permutation;
  • KK - count of the required largest values.

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

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

int compare (int x, int y);

where xx and yy are integers for which 1x,yN1 \leq x, y \leq N. The function returns xx, if px>pyp_x > p_y, and yy 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,KN, 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 000N = 100\ 000 in all tests
  • 1  K  100 0001\ \leq \ K\ \leq \ 100\ 000
  • The permutation pp 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 KK 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(1,authorScore+1yourScore+1)\min\left( 1,\frac{authorScore + 1}{yourScore + 1} \right)

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

The tests are distributed as follows

Percentage tests KK
14%14\% 1  K101\ \leq \ K \leq 10
20%20\% 10  K10010\ \leq \ K \leq 100
32%32\% 100  K1000100\ \leq \ K \leq 1000
20%20\% 1000 K100001000 \leq \ K \leq 10000
14%14\% 10000 K 10000010000 \leq \ K\ \leq 100000

Example

No Your program Jury's program
1. biggest (4, 2)
2. compare(1, 2) 1
3. compare(1, 3) 1
4. compare(1, 4) 1
5. compare(2, 3) 3
6. compare(3, 4) 3
7. return {1, 3}

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(41)=2yourScore = 5 - (4 - 1) = 2, authorScore=4(41)=1authorScore = 4 - (4 - 1) = 1 and that is how we calculate the ratio authorScore+1yourScore+1=1+12+1=23\frac{authorScore + 1}{yourScore + 1} = \frac{1 + 1}{2 + 1} = \frac{2}{3}.

Log in or sign up to be able to send submissions!