CF2127G2 题解

DaiRuiChen007 · 2025-10-07 20:05:27 · 题解

Problem Link

单个询问几乎没有信息，考虑两个近似排列答案的变化量。

如果没有 i\ne k 的限制，那么询问 q 的每个循环移位答案都不变，因为原本的 q_n 入边贡献必定减少，出边贡献必定增多。

那么加上 i\ne k 的限制，如果我们知道无限制时的答案，那么就能知道 q_k 的出边是否属于 q[k+1,n]。

不妨取 k=\lfloor \frac n2\rfloor+1，那么每次询问 q 就能知道每个 i 在 q 中与 p_i 的距离是否 \le n-k。

那么我们如果构造 \log n 个 q 使得对于每个 i，所有的 j 每次回答不完全相同。

记 b=q^{-1}，则对于任意 (x,y) 存在一个 b 使得 [b_y-b_i\le n-k]\ne [b_x-b_i\le n-k]（减法是 \bmod n 意义下的）。

如果 n 是偶数，我们可以按如下方式构造：初始 b_{d,i}=i，\forall i\in[1,\frac n2]，如果 i-1 的第 d 个二进制位是 1 就交换 b_i,b_{i+n/2}，其中 d\in[0,6]。

考虑任意的 (i,x,y)，我们要求存在一个 d 使得 x\bmod \frac n2,y\bmod \frac n2 的第 d 位相同或不同，由于 \frac n2<2^{6} 所以必定存在。
如果 n 是奇数，我们可以按如下方式构造：b_{d,i}=(i-1)\times 2^d\bmod n+1，其中 d\le [0,6]。

对于 (i,x,y)，只要某个 d 满足 2^d(x-y)\bmod n>\frac n2 就一定能得到不同的结果，很显然。

想要知道 q 在无限制下的答案，需要先确定任意一个 p_x=y。

如果 n 是偶数，设 n=2m，则询问 [q_1,\dots,q_{m},q_{m+1},\dots q_{2m}] 和 [q_{2m},q_{2m-1},\dots,q_m,q_{m+1},q_{m-1},q_{m-2}\dots q_1]，此时对于任意 i\ne q_{m+1}，i\to p_i 在两个排列中恰有一个产生贡献，除非 i=q_m,p_i=q_{m+1}。

那么我们固定 q_{m+1}，枚举 q_m 就能找到 p_x=q_{m+1} 的 x，具体来说找到两次询问之和 =n 的一个作为 x 即可。

如果 n 是奇数，那么固定 q_n=n，然后 q_m=1\sim n-1 都不满足的时候则 x=n，注意此时 q_m=x 时答案之和不一定是 n，要找和最大的一个作为 x。

因此可以在 2n 次操作内确定 (x,y)，然后 7n 次询问还原排列，总次数 2n+n\log_2n。

时间复杂度 \mathcal O(n^2\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[105][105],b[105],p[105],q[105],w[105];
int ask() {
    cout<<"?";
    for(int i=1;i<=n;++i) cout<<" "<<q[i];
    cout<<endl;
    int o; cin>>o; return o;
}
void solve() {
    cin>>n;
    int k=n/2+1,x=n,y=k; //find p[x]=y
    cout<<k<<endl;
    for(int i=1,m=n-(n&1),c=0;i<=m;++i) if(i!=k) {
        iota(q+1,q+n+1,1),swap(q[i],q[k-1]);
        int z=ask();
        reverse(q+1,q+m+1),swap(q[k],q[k-1]),z+=ask();
        if(i>1&&z>c) { x=i; break; }
        else if(c>z) { x=1; break; }
        else c=z;
    }
    memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
    iota(p+1,p+n+1,1);
    for(int d=0;d<7;++d) {
        if(~n&1) {
            iota(p+1,p+n+1,1);
            for(int i=1;i<=n/2;++i) if((i-1)>>d&1) swap(p[i],p[i+n/2]);
        }
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]|=((p[j]+n-p[i])%n<=n-k)<<d;
        for(int i=1;i<=n;++i) q[p[i]]=i;
        for(int i=1;i<=n;++i) w[q[k]]=ask(),rotate(q+1,q+2,q+n+1);
        int o=w[x]+((p[y]+n-p[x])%n<=n-k);
        for(int i=1;i<=n;++i) b[i]|=(o-w[i])<<d;
        if(n&1) for(int i=1;i<=n;++i) p[i]=(p[i]-1)*2%n+1;
    }
    for(int i=1;i<=n;++i) q[i]=find(a[i]+1,a[i]+n+1,b[i])-a[i];
    cout<<"!";
    for(int i=1;i<=n;++i) cout<<" "<<q[i];
    cout<<endl;
}
signed main() {
    int _; cin>>_;
    while(_--) solve();
    return 0;
}