24324번 - 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 ≤ x, y ≤ 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.

Write a function biggest(), 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.

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 ≤ x, y ≤ 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.

You must submit your biggest.cpp file to the system. The file should 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".

• N = 100 000 in all tests
• 1 ≤ K ≤ 100 000

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(1, (authorScore + 1) / (yourScore + 1))

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

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 (authorScore + 1)/(yourScore + 1) = (1+1)/(2+1) = 2/3.

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.