题解：P17854 [LBA-OI R6 B] 凌云沐雨

梦见云月 · 2026-11-07 18:39:39 · 题解

最多 n-1 次确定顺序，因此考虑逐个确定。

首先最简单的，对于 x,y，答案要么是 1，要么是 2，如果是 1 说明 x>y，否则 x<y。

假设我们当前有从小到大排好序的集合 S，满足 |S|=m，那么 \texttt{query(S)}=m。

考虑新增 A_{m+1}，比他小的无影响，比他大的都会向后指一位，而他会指向第一个比他大的元素的位置，这个是显然的。

容易发现这个 A_{m+1} 指向的就是我们查询到的结果，也是他在 S 中的位置。

所以我们就可以重复此过程，确定每个元素大小排序，最后还原原排列了。

#include <bits/stdc++.h>
using namespace std;
int n,k;
int ans[1000005];
vector<int>vec;
signed main(){
    cin>>n>>k;
    vec.push_back(1);
    for (int pos=2;pos<=n;pos++){
        int m=vec.size()+1;
        cout<<"? "<<m<<' ';
        for (int i=0;i<vec.size();i++){
            cout<<vec[i]<<' ';
        }
        cout<<pos<<endl;
        int c;
        cin>>c;
        vec.insert(vec.begin()+(c-1),pos);
    }
    for (int i=0;i<n;i++){
        ans[vec[i]]=i+1;
    }
    cout<<"!";
    for (int i=1;i<=n;i++){
        cout<<' '<<ans[i];
    }
    cout<<endl;

    return 0;
}