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

Solution Code:

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;

}