Problem Name: Chocolate Bunny

Problem Rating: 1600

Problem Link: https://mirror.codeforces.com/problemset/problem/1407/C

[If I make any mistake, please pardon me & correct me!]

In this problem, we can ask 2 indices(x,y) in 1 query & get P[x] mod P[y]. Our limitation is we can ask no more than 2*n queries. Here is the main trick! If we were allowed to ask n^2 queries, we could easily do it asking ? x y for each x (1->n) and each y (1->n except x)

e.g. if n=5, to get a[3] we can ask

?1 3

?2 3

?4 3

?5 3

All these results must be all numbers 1<=r<a[3](r can also be 0 for some numbers), so a[3]=max(all remainders)+1

But as we can ask no more than 2*n queries, we have to focus on the mathematical property of MOD.

Let's think about a mod b & b mod a: If a>b, then a mod b<b; and b mod a = b<b

So if we ask ? x y and ? y x, we get a[x]%a[y] and a[y]%a[x], Between these, the max one is the real one that exists in the Permutation & the min one is the changed remainder of the max one. So if a[x]%a[y]>a[y]%a[x], then P[x]=a[x], then x++ and compare x with the previous y.And if a[y]%a[x]>a[x]%a[y], P[y]=a[y], y=x, x++.[Here we are iterating over x] Thus we can get (n-1) numbers except the max one which we all know to be n.

Here Queries used 2*(n-1)=2*n-2

Complexity: O(2*n)

My Submission: https://mirror.codeforces.com/contest/1407/submission/320641205