题面
这是一道交互题。
有一个未知的长度为
N
\tt N
N 的排列
P
\tt P
P，已知
P
1
<
P
2
\tt P_1 < P_2
P1<P2 。
每次询问格式为 “
?
a
b
c
\tt?~a~b~c
? a b c ”，返回值为三元组
{
∣
P
a
−
P
b
∣
,
∣
P
b
−
P
c
∣
,
∣
P
a
−
P
c
∣
}
\tt \{|P_a-P_b|,|P_b-P_c|,|P_a-P_c|\}
{∣Pa−Pb∣,∣Pb−Pc∣,∣Pa−Pc∣} 的中位数。
在至多
2
n
+
420
\tt 2n+420
2n+420 次询问后，输出排列
P
\tt P
P，格式为 “
!
P
1
P
2
…
P
N
\tt!~P_1~P_2~\dots~P_N
! P1 P2 … PN ”。
然后每组数据会返回一个数，为
1
\tt1
1 则答案正确，为
−
1
\tt-1
−1 则错误，不要忘了输入这个数。
一共
t
(
1
≤
t
≤
1000
)
\tt t(1\leq t\leq1000)
t(1≤t≤1000) 组数据，保证
20
≤
N
≤
1
0
5
,
∑
N
≤
1
0
5
20\leq N\leq 10^5,\tt \sum N\leq 10^5
20≤N≤105,∑N≤105。
题解
有两种各占优势的做法。
Solution #1
首先，返回该三元组的中位数，相当于：若
P
a
>
P
b
>
P
c
\tt P_a>P_b>P_c
Pa>Pb>Pc，则返回
max
{
P
a
−
P
b
,
P
b
−
P
c
}
\tt\max\{P_a-P_b,P_b-P_c\}
max{Pa−Pb,Pb−Pc}。
有了这个简化，才能更好地继续推。
该解法的核心在于：如果已经知道了
1
\tt1
1 和
2
\tt2
2 的位置(假设为
P
A
,
P
B
\tt P_A,P_B
PA,PB)，那么可以在
n
−
2
\tt n-2
n−2 次操作后，确定整个排列。也就是分别询问
{
A
,
B
,
i
}
\tt\{A,B,i\}
{A,B,i}，所得值（
q
u
e
r
y
(
A
,
B
,
i
)
\tt query(A,B,i)
query(A,B,i)）
+
2
\tt+2
+2 便是
P
i
\tt P_i
Pi 了。
问题是怎么获得
1
\tt1
1 和
2
\tt2
2 的位置，或者说，也可以获得
N
\tt N
N 和
N
−
1
\tt N-1
N−1 的位置，总之通过
P
1
<
P
2
\tt P_1<P_2
P1<P2 确定最终答案。
经过一段尝试，我们发现，如果找到这么两个位置
a
\tt a
a 和
b
\tt b
b ，满足
∣
P
a
−
P
b
∣
≤
N
−
4
3
\tt|P_a-P_b|\leq \frac{N-4}{3}
∣Pa−Pb∣≤3N−4 ，处理出所有的
q
[
i
]
=
q
u
e
r
y
(
a
,
b
,
i
)
\tt q[i]=query(a,b,i)
q[i]=query(a,b,i) ，那么
q
[
i
]
\tt q[i]
q[i] 最大的
i
\tt i
i 就是
1
\tt1
1 或者
N
\tt N
N 的位置，
q
[
i
]
\tt q[i]
q[i] 严格次大的
i
\tt i
i 就是
2
\tt2
2 或者
N
−
1
\tt N-1
N−1 的位置。这样只需要多进行
N
−
2
\tt N-2
N−2 次操作。
那么，在剩下的
424
\tt424
424 次操作内，我们需要解决两个问题：
找到这样的位置
a
,
b
\tt a,b
a,b 。
找到
1
\tt1
1 和
2
\tt2
2 的或者
N
\tt N
N 和
N
−
1
\tt N-1
N−1 的位置
A
,
B
\tt A,B
A,B 。
找 a b:
我们可以证明：对于任意
13
\tt13
13 个位置，总存在
3
\tt3
3 个位置
x
,
y
,
z
\tt x,y,z
x,y,z ，满足
q
u
e
r
y
(
x
,
y
,
z
)
≤
n
−
4
6
\tt query(x,y,z)\leq\frac{n-4}{6}
query(x,y,z)≤6n−4（
⇒
max
{
∣
P
x
−
P
y
∣
,
∣
P
y
−
P
z
∣
,
∣
P
x
−
P
z
∣
}
≤
n
−
4
3
\tt\Rightarrow \max\{|P_x-P_y|,|P_y-P_z|,|P_x-P_z|\}\leq\frac{n-4}{3}
⇒max{∣Px−Py∣,∣Py−Pz∣,∣Px−Pz∣}≤3n−4）。
可以用反证法进行证明，即假设存在某
13
\tt13
13 个位置，满足
∀
{
x
,
y
,
z
}
,
max
{
∣
P
x
−
P
y
∣
,
∣
P
y
−
P
z
∣
,
∣
P
x
−
P
z
∣
}
>
n
−
4
3
\tt\forall \{x,y,z\},\max\{|P_x-P_y|,|P_y-P_z|,|P_x-P_z|\}>\frac{n-4}{3}
∀{x,y,z},max{∣Px−Py∣,∣Py−Pz∣,∣Px−Pz∣}>3n−4 。贪心地填数进去，你就会发现，刚好到
13
\tt13
13 个时，你就满足不了条件了。所以这种情况不存在，假设不成立。
找这
3
\tt3
3 个位置，需要枚举
(
13
3
)
=
286
\tt{13\choose3}=286
(313)=286 种情况，完全足够。
找到这样的
3
\tt3
3 个位置时，任选两个就可以作
a
,
b
\tt a,b
a,b 了。
找 A B:
我们会发现，假如你确定了某个
q
[
i
]
\tt q[i]
q[i] 最大的
A
\tt A
A 作为
1
\tt1
1 的位置，那么还是有两个位置可能为
2
\tt2
2 ，一个是真
2
\tt2
2 ，一个是
N
−
1
\tt N-1
N−1 ，令其分别为
B
1
,
B
2
\tt B_1,B_2
B1,B2 ，我们稍稍归纳一下就会发现：
q
u
e
r
y
(
A
,
B
1
,
a
)
≤
q
u
e
r
y
(
A
,
B
2
,
a
)
q
u
e
r
y
(
A
,
B
1
,
b
)
≤
q
u
e
r
y
(
A
,
B
2
,
b
)
{\tt query(A,B_1,a)\leq query(A,B_2,a)}\\ {\tt query(A,B_1,b)\leq query(A,B_2,b)}
query(A,B1,a)≤query(A,B2,a)query(A,B1,b)≤query(A,B2,b)
而且最多只有一个取等。因此便可以把
B
1
\tt B_1
B1 判断出来了。
CODE
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define DB double
#define LL long long
#define ENDL putchar('\n')
#define lowbit(x) ((-x) & (x))
#define INF 0x3f3f3f3f
LL read() {
LL f=1,x=0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
inline int ask(int a,int b,int c) {
cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
int as; cin>>as; return as;
}
int a[MAXN],p[MAXN],ar[MAXN];
vector<int> bu[MAXN];
int main() {
srand(time(0));
int T;cin>>T;
while(T --) {
cin>>n;
for(int i = 1;i <= n;i ++) bu[i].clear(),a[i] = 0,ar[i] = i;
random_shuffle(ar + 1,ar + 1 + n);
int A = 1,B = 2,C = 3,as,flag1 = 0;
for(A = 1;A <= 11;A ++) {
for(B = A+1;B <= 12;B ++) {
for(C = B+1;C <= 13;C ++) {
if((as=ask(A,B,C)) <= ((n-4)/6)) {
flag1 = 1; break;
}
}
if(flag1) break;
}
if(flag1) break;
}
int mi = n+1,ct = 1,ct2 = 0,ma = 0;
for(int i = 1;i <= n;i ++) {
if(i != A && i != B) {
a[i] = ask(A,B,i);
if(a[i] < mi) mi = a[i],ct = 1;
else if(a[i] == mi) ct ++;
if(a[i] == 2) ct2 ++;
ma = max(ma,a[i]);
bu[a[i]].push_back(i);
}
}
int H = bu[ma][0],H2 = bu[ma-1][0];
if((int)bu[ma-1].size() > 1) {
int H3 = bu[ma-1][1];
if(ask(H,H2,A) <= ask(H,H3,A) && ask(H,H2,B) <= ask(H,H3,B)) {
H2 = H2;
}
else H2 = H3;
}
p[H] = 1; p[H2] = 2;
for(int i = 1;i <= n;i ++) {
if(i != H && i != H2) {
p[i] = 2 + ask(H,H2,i);
}
}
if(p[1] > p[2]) {
for(int i = 1;i <= n;i ++) p[i] = n-p[i]+1;
}
cout<<"!";
for(int i = 1;i <= n;i ++) cout<<" "<<p[i];
cout<<endl;
int AC; cin>>AC;
}
return 0;
}
Solution #2
非常精妙的做法，不愧是
O
n
e
I
n
D
a
r
k
\tt OneInDark
OneInDark ！
主要是选择两对数来进行序列
q
\tt q
q 的确定，通过
q
\tt q
q 和
q
′
\tt q'
q′ 确定原序列。这里笔者就不展开了。原博客还是写了满大页的。
