https://atcoder.jp/contests/arc154/tasks/arc154_d
题解
首先,我们需要找到序列中 1 的位置,可以利用这样的性质:仅有 pi=1 满足对于任意的 j,pi+pi>pj 都不成立。所以可以利用 n−1 次询问找到 1 的位置。
然后,考虑 px+1>py 在 x=y 时等价于 px>py,所以每次询问 (x,1,y) 都可以得到 x,y 的大小关系。由此,直接利用归并排序就做完了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| #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; }
|