题目链接
首先不妨设 \(p _ a < p _ b < p _ c\) 则可以询问出 \(\max \{p _ b - p _ a, p _ c - p _ b\}\)。
首先可以花费至多 \(422\) 次操作确定一个三元组 \((x, y, z)\) 使得 \(p _ x, p _ y, p _ z\) 相差都不会太大，具体地最大减最小 \(\le (n - 4) / 3\)。
然后可以拿 \((x, y)\) 去对其他 \(n - 2\) 个数都问一遍，找出其中询问的最大值所在的位置 \(u\)，则 \(p _ u\) 一定是 \(1\) 或者 \(n\)。
然后我们希望找到 \(1, 2\) 或 \(n - 1, n\) 所在位置。发现在上面询问 \(n - 2\) 个数的过程中，把询问等于最大值 \(- 1\) 的所有位置找出来（不超过 2 个），然后拿 \((x, u)\) 去问这些位置，返回值最小的位置就是 \(p _ u\) 对应的另一个数。
由于我们不知道是 \(1, 2\) 还是 \(n - 1, n\)，先假设 \(p _ u = 1, p _ v = 2\)，再对其他 \(n - 2\) 个数都问一遍得出 \(p\) 数组。
因为题目保证 \(p _ 1 < p _ 2\)，所以出现 \(p _ 1 > p _ 2\) 的情况把值域反转一下就行了。
#include<cstdio>
#include<vector>
#include<array>
#include<random>
#define N 100005
#define ran(l,r) uniform_int_distribution<>(l,r)(rnd)
using namespace std;int T,n,p[N],d[N];
int ask(int x,int y,int z) {printf("? %d %d %d\n",x,y,z),fflush(stdout);int r=0; scanf("%d",&r);return r;
}
void fine() {printf("! ");for(int i=1;i<=n;i++) printf("%d ",p[i]);puts(""),fflush(stdout);
}
mt19937 rnd(random_device{}());
int main() {scanf("%d",&T);while(T--) {scanf("%d",&n);int x=0,y=0;while(1) {int p=ran(2,n-1),q=ran(1,p-1),r=ran(p+1,n);if(ask(p,q,r)<=(n-4)/6) {x=p,y=q; break;}}int mx=0,u=0;for(int i=1;i<=n;i++) if(i!=x&&i!=y) {d[i]=ask(x,y,i);if(d[i]>mx) mx=d[i],u=i;}vector<int> Ds;for(int i=1;i<=n;i++) if(i!=x&&i!=y&&d[i]==mx-1) Ds.push_back(i);int v=0,mn=n;for(auto D:Ds) {int w=ask(x,u,D);if(w<mn) mn=w,v=D;}p[u]=1,p[v]=2;for(int i=1;i<=n;i++) if(i!=u&&i!=v) p[i]=2+ask(u,v,i);if(p[1]>p[2]) {for(int i=1;i<=n;i++) p[i]=n+1-p[i];}fine(),scanf("%*d");}return 0;
}