怎么没题解呢，那就发一篇吧。

首先考虑有 3 个位置，标号为 $a,b,c$，两两询问得到 $x=\min\{a,b\},y=\min\{a,c\},z=\min\{b,c\}$。$x,y,z$ 三个值中一定有两个相等，且这个值是三数中最小的数。又因为所有值互不相等，所以可以确定最小值的位置（例如如果 $x=y$ 那么最小值位置在 $a$ 处）。

现在有前缀最大值 $a$ 和次大值 $b$ 和 $\min\{a,b\}$，每次新加入一个 $c$ 就可以通过两次询问确定一个值。

但是这样的构造操作次数是 $2\times n-1$ 的，无法通过。考虑丧失了哪些性质。对于某些 $c$ 不需要询问两次，如果询问得到的结果 $x$ 小于前缀次大值，那么三数中最小值是 $x$ 且位置在 $c$。

所以现在次数为 $O(n+\texttt{前缀次大值个数})$。序列前缀最大值个数期望是 $\ln n$，那么前缀次大值期望个数小于 $2\times \ln n$（期望 $\ln n$ 个数更新前缀最大值时次大值被更新，又期望 $\ln n$ 个数可能更新次大值），可以通过本题。

注意要打乱序列。

#include<bits/stdc++.h>
using namespace std;
const int N = 2000;
int n,a[N],ans[N];
inline int ask(int x,int y)
{
	int tmp;
	cout<<"? "<<x<<' '<<y<<endl;
	cin>>tmp;
	return tmp;
}
int x,y,xx,yy,zz;
bool t;
inline void work(int z)
{
	yy=ask(x,z);
	if(yy<xx)
	{
		ans[z]=yy;
		return;
	}
	zz=ask(y,z);
	if(xx==yy)
		ans[x]=xx,x=z,xx=zz;
	else if(yy==zz)
		ans[z]=yy;
	else//xx==zz
		ans[y]=xx,y=z,xx=yy;
}
mt19937 rd(time(0));
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=i;
	if(n==2)
	{
		int tmp=ask(1,2);
		ans[1]=ans[2]=tmp;
	}
	else
	{
		shuffle(a+1,a+1+n,rd);
		x=a[1],y=a[2];
		xx=ask(a[1],a[2]);
		for(int i=3;i<=n;i++)
			work(a[i]);
		int tmp=max({xx,yy,zz});
		ans[x]=ans[y]=tmp;
	}
	cout<<"! ";
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
	cout<<endl;
}

这么变态吗？

首先题目中的 $3000$ 给我们一个启发，就是一个位置最多需要两次查询得到。

这样，我们直接考虑对于三个不同的位置，假设不知道它们的值的情况下怎么两次出答案：

我们这样查询：$(i,j),(i,k)$，设第一个值为 $m_1$，第二个值为 $m_2$，不难做下面的分类讨论（前提是 $a_i$ 互不相同）：

• $m_1 = m_2$：即 $\min(a_i,a_j)=\min(a_i,a_k)$，如果前面一个是 $a_j$，后一个如果是 $a_i,a_k$ 都会与 $a$ 中元素互不相同冲突，所以一定是 $a_i = m_1 = m_2$；
• $m_1 > m_2$：即 $\min(a_i,a_j) > \min(a_i,a_k)$，如果前面一个是 $a_i$，如果后一个是 $a_i$，则与大于号矛盾，所以此时可以确定 $a_k$，而对于前面一个是 $a_j$，则后面一个同样是 $a_k$。
• $m_1 < m_2$：不难用 $m_1 > m_2$ 的逻辑，推出此时确定 $a_j$。

如此，就可以获得一共 $50$ 分。

然后对于那个 $n + 25$ 次以内，猜测是较松的 $n + \log n$，先使用记忆化，发现有一定的点通过，然后考虑到记忆化以后，次数做到 $n$ 加前缀最大值个数。

所以套上随机化一遍，此时期望在 $n + \ln n$ 左右，容易通过。