|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|0.4 초||1024 MB||370||0||0||0.000%|
Two players, A and B, play the following game. A comes up with a permutation p, p, ..., 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.
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:
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:
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.
1 ≤ K ≤ 10
10 ≤ K ≤ 100
100 ≤ K ≤ 1000
1000 ≤ K ≤ 10000
10000 ≤ K ≤ 100000
|№||Your program||Jury’s program|
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.
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.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)