enwisen

Description

Long ago, at the dawn of civilization, there lived an elephant. It was bipedal, with a cactus-like body and feet clad in technologically advanced footwear. This elephant was renowned for its wisdom. One day, an extravagant creature came to visit: a shark that had evolved four limbs, each equipped with similarly advanced footgear.

"O elephant," the shark beseeched, "make me wise!"

"Before I enwisen thee," the elephant replied, "thou must first complete my challenge."

The elephant has a secret permutation \(P\) of \(\{ 0, 1, \dots, N - 1 \}\). The elephant challenges the shark to recover this permutation by asking questions of two types, each with an associated cost:

1. Given three pairwise distinct indices \(i\), \(j\), and \(k\), what is the median of \(P[i]\), \(P[j]\), and \(P[k]\)? (Here, the median is the element which is neither the minimum nor the maximum). The cost of asking this question is \(1\).

2. Given two distinct indices \(i\) and \(j\), which one of \(P[i]\) and \(P[j]\) is smaller? The cost of asking this question is \(N\).

The lower the cost, the more delighted the elephant will be. Help the shark recover the secret permutation.

Implementation Details

You should implement the following procedure.

std::vector<int> recoverPermutation(int N)

• \(N\): the length of the permutation.
• This procedure should return an array \(Q\) of length \(N\), representing the elephant's secret permutation.
• This procedure is called exactly once for each test case.

The above procedure can make calls to the following two procedures to ask questions.

int getMedianValue(int i, int j, int k)

• \(i\), \(j\), \(k\): the indices to ask. It must be satisfied that \(0 \le i, j, k \le N - 1\) and that \(i\), \(j\), and \(k\) are pairwise distinct.
• This procedure returns the median of \(P[i]\), \(P[j]\), and \(P[k]\).

int getLess(int i, int j)

• \(i\), \(j\): the distinct indices to ask. It must be satisfied that \(0 \le i, j \le N - 1\) and \(i \neq j\).
• This procedure returns \(i\) if \(P[i] < P[j]\), and \(j\) otherwise.

Constraints

• \(4 \le N \le 60\,000\)
• The secret permutation \(P\) is valid. Formally, \(0 \le P[i] \le N - 1\) for \(0 \le i \le N - 1\), and \(P[i] \neq P[j]\) for \(0 \le i < j \le N - 1\).

Subtasks and Scoring

If in any of the test cases, the calls to the procedures do not conform to the rules above, or the return value of the procedure recoverPermutation is incorrect, the score of your solution for that test case will be \(0\).

Otherwise, in both subtasks, you can obtain a partial score. Let \(C\) be the total cost across all calls of getMedianValue and getLess. In subtask 1, the score is calculated as follows:

In subtask 2, the score is calculated as follows:

The plot below shows the number of points as a function of \(C\) your solution will get in subtask 2.

In particular, to achieve the following scores in subtask 2, your solution must have \(C\) be at most the following values.

Note that in some cases, the behaviour of the grader can be adaptive. This means that the value of \(P\) is not fixed in advance. Instead, the grader may freely change the value of \(P\) during execution, as long as there is at least one value of \(P\) consistent with all previous return values of getMedianValue and getLess.

Example

Consider the following call.

recoverPermutation(5)

This means that the \(P\) is a permutation of \(\{ 0, 1, 2, 3, 4 \}\). Suppose that for this example, \(P = [2, 4, 3, 0, 1]\).

The procedure may call getMedianValue as follows.

getMedianValue(0, 1, 2)

As the median of \(2\), \(4\), and \(3\) is \(3\), this procedure will return \(3\). The cost of this question is \(1\).

recoverPermutation may also call getLess as follows.

getLess(1, 3)

As \(P[1] > P[3]\), this procedure will return \(3\). The cost of this question is \(N = 5\).

The procedure recoverPermutation then returns \([2, 4, 3, 0, 1]\). The total score used across all questions is \(1 + 5 = 6\). Based on the scoring formulas mentioned above, full score is given.

Sample Grader

The sample grader is not adaptive. Instead, it receives \(P\) as its input.

Input format:

N
P[0] P[1] … P[N-1]

Output format:

Q[0] Q[1] … Q[N-1]
C

Here, \(Q\) is the permutation returned by recoverPermutation, and \(C\) is the total cost used by your solution across all questions.