For the index $$$j$$$ where $$$p_j = 1$$$, you must set $$$a_j$$$ to $$$1$$$ or $$$2n-1$$$.

In other words, $$$a_j$$$ will either be the minimum or maximum of the entire array.

So $$$a_j$$$ will be part of an inversion with every element to the left, or every element to the right.

For the index $$$j$$$ where $$$p_j = 1$$$, greedily set $$$a_j$$$ to $$$1$$$ or $$$2n-1$$$ depending on whether there would be less inversions to the left or to the right.

Then for the index $$$k$$$ where $$$p_k = 2$$$, do the same thing again. Although be careful counting because you should ignore index $$$j$$$ since it was already counted.

Repeat until you have constructed the answer. This works in $$$O(n^2)$$$ and should pass, or you can speed up to $$$O(n \log n)$$$ by counting with std::set or something like that.

Min/max abuse!

Minimum $$$x_i$$$ and maximum $$$x_j$$$.

Let $$$m$$$ equal the number of unique values in $$$x_i$$$. The length of the longest path in the graph (if it's a graph) cannot exceed $$$m-1$$$. (Why?)

$$$x_j - x_i$$$ is at least $$$m-1$$$. (Why?)

Do you see what to query first yet?

Query $$$x_i$$$ and $$$x_j$$$ first. If you:

• get $$$ \lt m-1$$$, then you definitely have a graph
• get $$$ \gt m-1$$$, then you definitely have points in the plane
• get $$$m-1$$$, then you could have either, but you have 1 query left.

If we have a graph, and $$$i \rightarrow j$$$ has length $$$m-1$$$, what does this say about $$$j \rightarrow i$$$?

For the first query see above.

For the second query we'll query $$$x_j$$$ and $$$x_i$$$ (same as the first time but in the reversed order).

If we have a graph, we either:

• $$$i, j$$$ not connected: we'll get 0.
• $$$i, j$$$ are connected in a cycle, in which case we have to get 1, because the path $$$i \rightarrow ... \rightarrow j$$$ visits every vertex. If there was another vertex between $$$j$$$ and $$$i$$$, that would be a contradiction, since there would now be a shorter path from $$$i$$$ to $$$j$$$.

Otherwise, we'll get a number $$$\ge m-1$$$ for the distance.

The statement seems pretty diabolical. Let's try to do something: maybe sort $$$a$$$?

If you sort $$$a$$$, then the resulting array $$$b$$$ should also be sorted.

Because if $$$b_i \le b_j$$$, then if an index works for $$$i$$$, it will also work for $$$j$$$, so $$$a_i \le b_i$$$.

Think about min/max abuse. Specifically, min/max abuse on the array $$$b$$$ you're constructing.

There must be a unique absolute-value min/max. For example, if $$$-n$$$ is in $$$b$$$, then the problem conditions prevent $$$n$$$ from being in $$$b$$$.

The unique absolute-value min/max either

• has $$$a_i = n$$$, because it's too positive for anything to make it $$$ \lt 0$$$;
• or has $$$a_i = 0$$$, because it's too negative for anything to make it $$$ \gt 0$$$.

So we can place either $$$-n$$$ at the left, or $$$n$$$ at the right.

For each step, we'll either place $$$-n$$$ at the left if $$$a_l = 0$$$, or $$$n$$$ at the right if $$$a_r = n$$$. Note that if both $$$a_l = 0, a_r = n$$$, then that's a contradiction.

Continue for $$$n-1$$$. Note that all the higher positive numbers we placed before are guaranteed to work with us, and all the lower negative numbers we placed are guaranteed to not. So other than that the subproblem is independent.

Note: don't look at my accepted submission, check the official one instead. I used a slightly different method of filling it in at the time.

First try to find any polynomial time solution.

$$$1$$$ has to be in the permutation $$$p$$$ somewhere.

If $$$1$$$ is placed at position $$$i \in [1...n]$$$, then $$$a_i = (i) \cdot (n-i+1)$$$.

Additionally, if there are multiple valid locations to place the $$$1$$$, that's a contradiction. (Why?)

Now that you know the location of $$$1$$$, solve the left and right half.

The left and right half are independent because crossing the minimum $$$1$$$ forces the subarray minimum to be less than $$$p_i$$$.

Recursively solve the left and right half. Then merge the answers (assuming the current size is $$$n$$$ and the minimum occurs at index $$$i$$$:

We multiply by the choose because you can choose any distribution of the $$$n-1$$$ remaining numbers across the left and right half.

Also check for contradictions if any $$$a_i$$$ is too large (exceeds what would be possible even if it was a minimum).

Then optimizing to $$$n \log n$$$ involves searching for the $$$a_i$$$ location from outside to inside. See the official editorial for more details.

Here is my somewhat crappy code