Median Queries
题解
首先，我们得找到两个相差不超过
⌊
n
−
1
3
⌋
\left\lfloor\frac{n-1}{3}\right\rfloor
⌊3n−1⌋的点。
如果我们找到了一个三元组使得
(
a
,
b
,
c
)
⩽
⌊
n
−
1
6
⌋
(a,b,c)\leqslant \left\lfloor\frac{n-1}{6}\right\rfloor
(a,b,c)⩽⌊6n−1⌋，那么一定有
∣
a
−
b
∣
⩽
⌊
n
−
1
3
⌋
\left|a-b\right|\leqslant \left\lfloor\frac{n-1}{3}\right\rfloor
∣a−b∣⩽⌊3n−1⌋。
可以发现，对于任意
13
13
13个数，它们之中一定存在三元组
(
a
,
b
,
c
)
(a,b,c)
(a,b,c)使得
∣
a
−
b
∣
⩽
⌊
n
−
4
3
⌋
\left|a-b\right|\leqslant \left\lfloor\frac{n-4}{3}\right\rfloor
∣a−b∣⩽⌊3n−4⌋
可以通过考虑不同元素间的间隙求出，因为
6
⋅
⌊
n
−
4
3
⌋
+
13
=
n
+
10
>
n
6\cdot\left\lfloor\frac{n-4}{3}\right\rfloor+13=n+10>n
6⋅⌊3n−4⌋+13=n+10>n，所以无论怎样，都必定会存在这样的三元组。
找到这样三元组的次数是
(
13
3
)
=
286
<
420
\binom{13}{3}=286< 420
(313)=286<420，但其实直接随机找的话
420
420
420次也可以找到，毕竟概率还是挺高的。
找到这样的三元组后，我们可以对每一个
x
≠
a
∧
x
≠
y
x\not =a\wedge x\not = y
x=a∧x=y都求出
(
a
,
b
,
x
)
(a,b,x)
(a,b,x)。
由于最后有
p
1
<
p
2
p_{1}<p_{2}
p1<p2的条件，所以无论
a
>
b
a>b
a>b还是
a
<
b
a<b
a<b其实都是没关系的，反正最后可以调整得到答案，这里不妨设
a
⩽
b
a\leqslant b
a⩽b。
由于
a
−
1
>
b
−
a
a-1> b-a
a−1>b−a与
n
−
b
>
b
−
a
n-b>b-a
n−b>b−a中必定有一个成立，所以我们只需要找到最大的
(
a
,
b
,
x
)
(a,b,x)
(a,b,x)，那么
x
x
x就是
1
1
1或者
n
n
n，而次大的
(
a
,
b
,
x
)
(a,b,x)
(a,b,x)的
x
x
x就是
n
−
1
/
1
n-1/1
n−1/1或者
2
/
n
2/n
2/n。
假设我们的
x
x
x为
1
1
1(由于后面会调整，即使把
n
n
n当作
1
1
1也没关系)，设这两个值为
y
1
y1
y1，
y
2
y2
y2，我们可以通过比较
(
1
,
y
1
,
a
)
(1,y1,a)
(1,y1,a)与
(
1
,
y
2
,
a
)
(1,y2,a)
(1,y2,a)来得到哪个是
2
2
2。
很明显，
(
1
,
2
,
a
)
=
a
−
2
<
(
1
,
n
,
a
)
=
a
−
1
(1,2,a)=a-2<(1,n,a)=a-1
(1,2,a)=a−2<(1,n,a)=a−1，所以小的那个就是
2
2
2。
既然我们得到了
1
1
1与
2
2
2，那么对于其余任意一个询问
(
1
,
2
,
x
)
(1,2,x)
(1,2,x)，必然有
(
1
,
2
,
x
)
=
x
−
2
(1,2,x)=x-2
(1,2,x)=x−2，所以我们就可以求出其余的位置上的值。
然后再判断
p
1
p_{1}
p1与
p
2
p_{2}
p2之间的大小关系，若
p
1
>
p
2
p_{1}> p_{2}
p1>p2，那么就说明我们找到的
1
1
1实际上是
n
n
n，再将整个序列都翻转一下就可以了。
时间复杂度 O ( n ) O\left(n\right) O(n)，总询问次数 O ( 2 n + 284 ) O\left(2n+284\right) O(2n+284)，其实题目还是很宽松的。
源码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=998244353;
const int zero=500;
const LL jzm=2333;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
int n,t,maxx,p[MAXN];
vector<int>vec[MAXN];
int Ask(int a,int b,int c){printf("? %d %d %d\n",a,b,c);fflush(stdout);int res;read(res);return res;}
signed main(){
read(t);
while(t--){
read(n);bool flag=0;int a1,b1;maxx=0;
for(int i=1;i<=11;i++){
for(int j=i+1;j<=12;j++){
for(int k=j+1;k<=13;k++)
if(Ask(i,j,k)<=(n-4)/6){flag=1;a1=i,b1=j;break;}
if(flag)break;
}
if(flag)break;
}
for(int i=1;i<=n;i++)
if(a1!=i&&b1!=i){
int tmp=Ask(a1,b1,i);
vec[tmp].push_back(i);
maxx=max(maxx,tmp);
}
int p1=vec[maxx][0],p2;
if(vec[maxx-1].size()==1)p2=vec[maxx-1][0];
else p2=Ask(a1,p1,vec[maxx-1][0])<Ask(a1,p1,vec[maxx-1][1])?vec[maxx-1][0]:vec[maxx-1][1];
p[p1]=1;p[p2]=2;for(int i=1;i<=n;i++)if(i!=p1&&i!=p2)p[i]=Ask(p1,p2,i)+2;
if(p[1]>p[2])for(int i=1;i<=n;i++)p[i]=n-p[i]+1;
printf("!");for(int i=1;i<=n;i++)printf(" %d",p[i]);puts("");fflush(stdout);
int res;read(res);if(res==-1)return 0;
for(int i=1;i<=n;i++)vec[i].clear();
}
return 0;
}