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->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\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>b$, then $a \bmod b<b$; and $b \bmod a = b> 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]>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]<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:↵
↵
```c++↵
#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;↵
}↵
```↵
------------------↵
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->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\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>b$, then $a \bmod b<b$; and $b \bmod a = b> 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]>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]<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:↵
↵
```c++↵
#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;↵
}↵
```↵
