题目概述

交互题。有一个 $1\sim n$ 的排列 $\{p_n\}$ ，每次可以询问 $(x,y)$ ，得知 $p_x\bmod p_y$ 。在 $2n$ 次询问内问出这个排列。

解题报告

考虑两个数 $A,B(A\not=B)$ 之间取模：

• 如果 $A<B$ ，则 $A\bmod B=A,B\bmod A<A$
• 如果 $A>B$ ，则 $A\bmod B<B,B\bmod A=B$

因此两个不相等数之间只需要问两次就可以得知小的那一个。

所以只需要每次挑出两个还没确定的位置就可以问出其中一个了，总共需要问 $2(n-1)$ 次。

用并查集快速查找还没确定的位置，用链表也行。

示例程序

#include<cstdio>
using namespace std;
const int maxn=10000;

int n,a[maxn+5],fat[maxn+5];bool vis[maxn+5];

void Ask(int x,int y) {printf("? %d %d\n",x,y);fflush(stdout);}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n+1;i++) fat[i]=i;
    for (int t=1;t<n;t++){
        int i=getfa(1),j=getfa(i+1);
        int A;Ask(i,j);scanf("%d",&A);
        int B;Ask(j,i);scanf("%d",&B);
        if (A<B) a[j]=B,vis[B]=true,fat[j]=getfa(j+1);
        if (A>B) a[i]=A,vis[A]=true,fat[i]=getfa(i+1);
    }
    for (int i=1;i<=n;i++) if (!vis[i]) a[getfa(1)]=i;
    putchar('!');for (int i=1;i<=n;i++) printf(" %d",a[i]);puts("");
    return 0;
}