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

ww3733a · 2026-11-09 19:40:44 · 题解

询问次数最大为 n-1，可以大概猜到交互策略：询问 n-1 个序列，每次确定一个相对关系。

假设当前我们已经确定了 i-1 个数的大小关系，维护 p_1,p_2,\ldots,p_{i-1}，满足 A_{p_1}<A_{p_2}<\cdots<A_{p_{i-1}}。

现在要确定第 i 个数的位置，把第 i 个数直接放到序列的后面，设它离散后的位置为 x。则序列离散化后变为是 1,2,\ldots,x-1,x+1,\ldots,i,x，前面 x-1 个数字各自成环，其余的成一个环，环的数量就是 x。这样可以通过询问环的数量得到其位置，每次把 p_i 放到应在的位置上，保持升序。重复执行操作（从 2 到 n），即可得到 p 数组。

最终输出需要把 p 数组还原，即 A_{p_i}=i。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
/*=====================*/
using ll=long long;
#define endl '\n'
/*=====================*/
const int N=1e3+10;
/*=====================*/
int p[N],ans[N];
/*=====================*/
void Solve(void) {
    int n,t; cin>>n>>t;
    p[1]=1;
    for(int i=2;i<=n;i++) {
        cout<<"? "<<i<<' ';
        for(int j=1;j<i;j++) cout<<p[j]<<' ';
        cout<<i<<'\n';
        cout.flush();
        int x; cin>>x;
        for(int j=i;j>x;j--) p[j]=p[j-1];
        p[x]=i;
    }
    for(int i=1;i<=n;i++) ans[p[i]]=i;
    cout<<"! ";
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
}
/*=====================*/
signed main() {
#ifndef ONLINE_JUDGE
    // freopen("../IN.txt","r",stdin);
#endif
    // freopen("filename.in","r",stdin);
    // freopen("filename.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);

    // int T; cin>>T; while(T--)
    Solve();
    return 0;
}

::::