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} \bmod P_{y}$$$. Our limitation is we can ask no more than $$$2\cdot 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- \gt n)$$$ and each $$$y (1- \gt 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 \lt =r \lt 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\cdot n$$$ queries, we have to focus on the mathematical property of $$$MOD$$$.

Let's think about $$$a \bmod b$$$ & $$$b \bmod a$$$: If $$$a \gt b$$$, then $$$a \bmod b \lt b$$$; and $$$b \bmod a = b \gt a \bmod b$$$

So if we ask ? x y and ? y x, we get $$$a[x]\bmod a[y]$$$ and $$$a[y]\bmod 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]\bmod a[y] \gt a[y]\bmod a[x]$$$, then $$$P[x]=a[x]$$$, then $$$x++$$$ and compare $$$x$$$ with the previous $$$y$$$.And if $$$a[x]\bmod a[y] \lt a[y]\bmod a[x]$$$, $$$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\cdot (n-1)=2\cdot n-2$$$

Complexity: $$$O(2\cdot n)$$$

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

Solution:

#include<bits/stdc++.h>
using namespace std;


#define TT1 int TC=1;for(int ti=1;ti<=TC;ti++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int main()
{
    fastio
    TT1
    {
        int n;
        cin>>n;
        int a[n+1];
        for(int i=1;i<=n;i++)a[i]=n;
        int j=1;
        for(int i=2;i<=n;i++){
            int r1,r2;
            cout<<"? "<<j<<" "<<i<<endl;
            cin>>r1;
            cout<<"? "<<i<<" "<<j<<endl;
            cin>>r2;
            if(r1>r2){
                a[j]=r1;
                j=i;
            }
            else{
                a[i]=r2;
            }

        }
        cout<<"! ";
        for(int i=1;i<=n;i++)cout<<a[i]<<" ";
            cout<<endl;

        
    }
    return 0;
}