题解：P14227 [ICPC 2024 Kunming I] 排列

· · 题解

题目分析

这是一道对思维、码力均有一定要求的题。不难想到 1\sim n 逐个二分定位，但是由于每个询问都要填满，开头不容易处理，可以采用暴力。询问次数为 1000+\sum_{i=1}^{999}\log_2i\approx9519 次，不能通过本题。

考虑合并询问。注意到二分的区间要么相等，要么无交，可以两数同时二分定位。如果区间相等，就猜测两数一左一右；如果区间无交，同样可以猜测两数一左一右。有 \frac12 的概率两个同时猜对或猜错，只需要一次询问，另外 \frac12 的概率恰好猜对一个，需要额外一次询问，平均询问次数为 \frac32。询问次数为 1000+\sum_{i=1}^{499}\frac32\log_2(2i)\approx7386，不能通过本题。

询问次数中的 1000 很大，必须消掉。可以将前两个数放在一起二分定位，通过拒绝采样的方法，得到一左一右的两数，这样就解决了空的地方怎么填的问题。拒绝采样成功率为 \frac12，平均采样次数为 2。询问次数为 1+\sum_{i=1}^{500}\frac32\log_2(2i)\approx6402，可以通过本题。

AC Code

代码实现很复杂，省略一些几乎复制粘贴的片段。本地实测询问次数在 6512 左右。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,res,a[N],b[N],c[N];
random_device rd;
mt19937 gen(rd());
void query(){
    cout<<'0';
    for(int i=1;i<=n;i++)cout<<' '<<b[i];
    cout<<endl;
    cin>>res;
}
int main(){
    cin>>n;
    if(n==1){
        cout<<"1 1";
        return 0;
    }
    for(int i=1;i<=n;i++)a[i]=i;
    for(;;){
        shuffle(a+1,a+n+1,gen);
        for(int i=1;i<=n>>1;i++)b[i]=a[1];
        for(int i=(n>>1)+1;i<=n;i++)b[i]=a[2];
        query();
        if(res==1)continue;
        if(!res)swap(a[1],a[2]);
        int l1=1,r1=n>>1,l2=(n>>1)+1,r2=n;
        while(l1<r1&&l2<r2){
            int mid1=l1+r1>>1,mid2=l2+r2>>1;
            for(int i=1;i<=n>>1;i++)b[i]=a[2];
            for(int i=(n>>1)+1;i<=n;i++)b[i]=a[1];
            for(int i=l1;i<=mid1;i++)b[i]=a[1];
            for(int i=l2;i<=mid2;i++)b[i]=a[2];
            query();
            if(res==2){
                r1=mid1,r2=mid2;
                continue;
            }
            if(!res){
                l1=mid1+1,l2=mid2+1;
                continue;
            }
            for(int i=l2;i<=mid2;i++)b[i]=a[1];
            query();
            if(res)r1=mid1,l2=mid2+1;
            else l1=mid1+1,r2=mid2;
        }
        while(l1<r1){
            /*省略*/
        }
        while(l2<r2){
            /*省略*/
        }
        c[l1]=a[1],c[l2]=a[2];
        break;
    }
    if(n==2){
        cout<<"1 "<<c[1]<<' '<<c[2]<<'\n';
        return 0;
    }
    for(int o=3;o<n-1;o+=2){
        int l1=1,r1=n-o+1,l2=1,r2=n-o+1;
        while(l1<r1&&l2<r2){
            int mid1=l1+r1>>1,mid2=l2+r2>>1;
            fill(b+1,b+n+1,a[1]);
            for(int i=1,j=1;i<=n;i++){
                if(c[i])continue;
                if(j>=l1&&j<=mid1)b[i]=a[o];
                if(j>mid2&&j<=r2)b[i]=a[o+1];
                j++;
            }
            query();
            if(--res==2){
                r1=mid1,l2=mid2+1;
                continue;
            }
            if(!res){
                l1=mid1+1,r2=mid2;
                continue;
            }
            /*省略*/
        }
        while(l1<r1){
            /*省略*/
        }
        while(l2<r2){
            /*省略*/
        }
        /*省略*/
    }
    if(~n&1){
        /*省略*/
    }
    int i=1;
    while(c[i])i++;
    c[i]=a[n];
    cout<<'1';
    for(int i=1;i<=n;i++)cout<<' '<<c[i];
}