Sim2 | sqsort

Rado dislikes writing problem statements, so we will keep this one short. The problem is interactive and the system has an array of integers $A_{0}, A_{1}, ..., A_{N - 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 $\left( i_{0},j_{0} \right),\left( i_{1},j_{1} \right),\ldots,(i_{\frac{N\left( N + 1 \right)}{2} - 1\ },j_{\frac{N\left( N + 1 \right)}{2} - 1})$ such that:

1) For all $0 \leq i^{'} \leq j^{'} < N$, there exists a position $0 \leq k < \frac{N\left( N + 1 \right)}{2}$ , such that $(i^{'},j^{'}) = (i_{k},j_{k})$.

2) $A_{i_{k - 1}} + A_{j_{k - 1}} \leq A_{i_{k}} + A_{j_{k}}$ for all $1 \leq k < \frac{N\left( N + 1 \right)}{2}$.

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 \leq a,b,c,d < N$, you can ask whether $A_{a} + A_{b} < A_{c} + A_{d}$. You want to ask as few questions as possible.

Implementation details

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 $A_{a} + A_{b} < A_{c} + A_{d}$, and false otherwise. The condition $0 \leq a,b,c,d < N$, should hold for all queries your program performs.

You should write a program 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.

Constraints

• $100 \leq N \leq 2 \ 000$

Scoring

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:

• $0$ points, if $Q > 5 \times 10^{7}$ or if the sequence returned by solve is not sorted as described above
• $\min\left( 1,\left( \frac{2N^{2} + 1}{Q + 1} \right)^{1.25} \right) \times P$ where $P$ is the maximum possible score for the test, otherwise

Local testing

You 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 $A_{0},A_{1},...,A_{N - 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.

Example

Explanation

1. $N = 3$. The array $А$ is equal to $\left\{ 5,\ 1,\ 3 \right\}$ but the solve function is not given this.
2. $A_{0} + A_{1} = 6 < 10 = A_{0} + A_{0}$
3. $A_{0} + A_{2} = 8 < 10 = A_{0} + A_{0}$
4. $A_{0} + A_{2} = 8 \geq 6 = A_{0} + A_{1}$
5. $A_{1} + A_{2} = 4 \geq 2 = A_{1} + A_{1}$
6. $A_{2} + A_{2} = 6 \geq 4 = A_{1} + A_{2}$
7. $A_{1} + A_{1} = 2 < 6 = A_{0} + A_{1}$
8. $A_{1} + A_{2} = 4 < 6 = A_{0} + A_{1}$
9. $A_{2} + A_{2} = 6 \geq 6 = A_{0} + A_{1}$
10. $A_{2} + A_{2} = 6 < 8 = A_{0} + A_{2}\$
11. $A_{1} + A_{1} \leq A_{1} + A_{2} \leq A_{0} + A_{1} \leq A_{2} + A_{2} \leq A_{0} + A_{2} \leq A_{0} + A_{0}$

The program used 9 queries and managed to correctly sort the sequence.