Codeforces Round #720 Nastia and a Hidden Permutation - Java/C++

Solution:

For first type of query, every time we take x as n-1. For second type of query, every time we take x as 1. So, when $p_i$ and $p_j$ not equals to 1 or 2 or n-1 or n, the first query is equivalent to $\max{(p_i, p_j)}$. And the second query is equivalent to $\min{(p_i, p_j)}$.


Normal Case:

So, for most of cases. Based on the two queries above, we can do another query to get the exact value of $p_i$ and $p_j$: $$min{(\max{(x, p_i)}, \max{(x + 1, p_j)})},\ which\ x=\min{(p_i, p_j)}$$

For the third query: because $x=\min{(p_i, p_j)}$.
So, if and only if $$p_j>p_i=x=\min{(p_i, p_j)}$$there are: $$min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}=\min{(p_i, p_j)}=x=p_i$$

So, we can get the smaller one of the $i$ and $j$ through the third query. So, also get the bigger one of the $i$ and $j$


Special Case:

Now let us consider the case which $p_i$ and $p_j$ equals 1 or 2 or n-1 or n.

Easy to find that: if $\min{(\max{(1, p_i)}, \max{(2, p_j)})}=1$, then $p_i$ must be 1. But note that, the result of this case is same to the normal case.

When $\min{(\max{(1, p_i)}, \max{(2, p_j)})}=2$, we suspect if $p_j$ equals 1 or not. So, we swap $i$ and $j$ and query again.
If $p_j$ not 1, then one of $p_i$ and $p_j$ must be 2. But still same with the normal case.

So, the only thing we need change from the normal case is the case below:
When $\min{(\max{(1, p_i)}, \max{(2, p_j)})}=2$ and $\min{(\max{(1, p_j)}, \max{(2, p_i)})}=1$
We need change the $p_j$ from 2 to 1.

The same, when $\max{(\min{(n-1, p_i)}, \min{(n, p_j)})}=n-1$ and $\max{(\min{(n-1, p_j)}, \min{(n, p_i)})}=n$, change the $p_i$ to n.


Code:

C++:

Submission #115929143 - Codeforces
Codeforces. Programming competitions and contests, programming community

Java:

Submission #115626975 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge