题目链接

题目大意

有一个长度为n的全排列，你可以询问2n次，要你经过这个2n次的询问后，求出这个全排列

询问定义为：输入"? i j"输出\(p_{i} mod p_{j}\)

题目思路

比赛的时候想了很久都没思路，一直想的是用O(n)的方法确定出这个全排列n的位置，然后再用O(n)用其他位置的数去模它。结果一直没写出来。

这个题目的思路其实就是两个数互模，那么大的的那个模数必然是这两个数中的小的那个数

然后题目就变得简单起来，每2次查询就能确定一个值，然后再用另外一个不确定的值去和其他数互模，显然最后剩下来的就是那个最大的数n

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define fi first
#define se second
#define debug printf(" I am here\n");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
int n,a[maxn];
signed main(){
    scanf("%d",&n);
    int st=1;
    for(int i=2,x,y;i<=n;i++){
        printf("? %d %d\n",st,i);
        fflush(stdout);
        scanf("%d",&x);
        printf("? %d %d\n",i,st);
        fflush(stdout);
        scanf("%d",&y);
        if(x>y){//a[st]<a[i]
           a[st]=x;
           st=i;
        }else{
            a[i]=y;
        }
    }
    a[st]=n;
    printf("! ");
    for(int i=1;i<=n;i++){
        printf("%d%c",a[i],i==n?'\n':' ');
    }
    fflush(stdout);
    return 0;
}