시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 10 | 1 | 1 | 100.000% |
Rado dislikes writing problem statements, so we will keep this one short. The problem is interactive and the system has an array of integers A0, A1, ..., AN−1. Unfortunately, you only know its length and not the values it contains. The goal is to sort all unordered pairs of positions such that the sums of their respective array elements are non-decreasing. Formally, we want to find a sequence (i0, j0), (i1, j1), … , (iN(N+1)/2−1, jN(N+1)/2−1) such that:
Since you don’t know the values in A, you’ll be able to ask the jury questions to compare the sum of one pair of elements to the sum of another pair of elements. More formally, for some tuple 0 ≤ a, b, c, d < N, you can ask whether Aa + Ab < Ac + Ad. You want to ask as few questions as possible.
Your program should implement a solve
function that will be called exactly once and should the sorted sequence of pairs. Its prototype must be:
std::vector<std::pair<int, int>> solve(int n);
Your program can repeatedly call the function cmp, which has the following prototype:
bool cmp(int a, int b, int c, int d);
We refer to a call of this function as a query and it returns true, if Aa + Ab < Ac + Ad, and false otherwise. The condition 0 ≤ a, b, c, d < N, should hold for all queries your program performs.
You should write a program called sqsort.cpp, which implements the solve function but it must not contain a main function. Also, it must not interact with the standard input and output and it should include the header file sqsort.h using the following preprocessor directive:
#include "sqsort.h"
As long as it fulfills these conditions, your program can contain any sort of helper functions, classes, variables, etc.
Every test is scored separately and the number of points you’ll receive for it depends on the number of queries Q your program has performed before returning the sorted sequence:
solve
is not sorted as described aboveYou are provided with the files sqsort.h and Lgrader.cpp, which you can compile together with your program. On starting, the program will read an integer N, followed by an array of integers A0, A1, ..., AN−1. Then it will call your solve
function and answer its cmp
queries. Finally, it will print the total number of queries your program used to produce a sorted sequence or a message that the sequence is not sorted. You can modify these files however you want. The jury’s grader is guaranteed to behave equivalently to Lgrader.cpp and will not adapt to your queries.
№ | Actions of sqsort |
Actions and responses of the jury |
---|---|---|
1. | solve(3) |
|
2. | cmp(0, 1, 0, 1) |
return true |
3. | cmp(0, 2, 0, 0) |
return true |
4. | cmp(0, 2, 0, 1) |
return false |
5. | cmp(1, 2, 1, 1) |
return false |
6. | cmp(2, 2, 1, 2) |
return false |
7. | cmp(1, 1, 0, 1) |
return true |
8. | cmp(1, 2, 0, 1) |
return true |
9. | cmp(2, 2, 0, 1) |
return false |
10. | cmp(2, 2, 0, 2) |
return true |
11. | return {(1, 1), (1, 2), (0, 1), (2, 2), (0, 2), (0, 0)} |
The program used 9 queries and managed to correctly sort the sequence.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)