AtCoder Regular Contest 154 D

https://atcoder.jp/contests/arc154/tasks/arc154_d

题解

首先，我们需要找到序列中 1 的位置，可以利用这样的性质：仅有 $p_i=1$ 满足对于任意的 $j$，$p_i+p_i>p_j$ 都不成立。所以可以利用 $n-1$ 次询问找到 $1$ 的位置。

然后，考虑 $p_x+1>p_y$ 在 $x\neq y$ 时等价于 $p_x>p_y$，所以每次询问 $(x,1,y)$ 都可以得到 $x,y$ 的大小关系。由此，直接利用归并排序就做完了。

代码

#include <bits/stdc++.h>
using namespace std;
int pos=1,id[2005],ans[2005];
int ask(int i,int j,int k)
{
    cout<<"? "<<i<<' '<<j<<' '<<k<<endl;
    string s;cin>>s;
    return s=="Yes";
}
bool cmp(int x,int y)
{
    return ask(y,pos,x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=2;i<=n;i++)
        if(ask(pos,pos,i)) pos=i;
    for(int i=1;i<=n;i++) id[i]=i;
    stable_sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++) ans[id[i]]=i;
    cout<<"!";
    for(int i=1;i<=n;i++) cout<<" "<<ans[i];
    cout<<endl;
    return 0;
}