Rapid

Task

Marius has a secret permutation $p_1, p_2, \ldots, p_n$. Although Marius does not want to reveal the values of the elements in the permutation, he is willing to answer a limited number of queries of the following type:

• compare(i, j) ($1 \le i, j \le n$, $i \ne j$) — Returns the minimum value between $p_i$ and $p_j$.

Your task is to find the positions of the numbers $n - 1$ and $n$ in Marius' permutation.

If $p_i = n - 1$ and $p_j = n$, then both $(i, j)$ and $(j, i)$ are considered correct answers.

Implementation

You need to implement the function:

std::pair<int, int> find_positions(int n);

Where:

• $n$ is the size of the permutation.
• Your function should return a pair of integers representing the positions (1-indexed) of the values $n$ and $n-1$, in any order.

To interact with Marius' permutation, you can use the following function provided by the grader:

int compare(int i, int j);

This function returns $\min(p_i, p_j)$.

• You may call this function up to $lim$ times per test case.
• If you exceed the allowed number of queries, your program will receive a Wrong Answer.

Constraints and Clarifications

• The permutation $p$ is a permutation of integers from $1$ to $n$.
• The permutation is fixed for the duration of a test case.
• The number of queries used affects the score (see Scoring below).
• All indices are 1-based.
• Any valid pair of indices where one holds $n$ and the other holds $n - 1$ is considered correct.
• You must #include "rapid.h"

Example

Suppose the hidden permutation is [3, 1, 5, 2, 4], so $n = 5$.

Then your function might call:

compare(1, 2); // returns 1
compare(1, 3); // returns 3
compare(3, 5); // returns 4

From these, you can deduce:

• $p_3 = 5$ (which is $n$)
• $p_5 = 4$ (which is $n - 1$)

Then, you return:

return {3, 5}; // or {5, 3}

Scoring

Let $q$ be the number of compare calls used in a test case. Then your score for that test case will be:

• 1 if $q \le 10\,000$
• $\frac{\text{lim} + 1 - q}{\text{lim} + 1 - 10\,000}$ if $10\,000 < q \le \text{lim}$
• 0 if $q > \text{lim}$

Subtasks

Notes

• After each call to compare(i, j), the return value is immediately available.
• The total number of test cases is $t = 25$.
• You may assume that the grader resets the hidden permutation for each test case.
• If your solution fails any test case, your submission will be considered incorrect.