题解：P14828 彻彻崩

· · 题解

考虑状压套二分。每次枚举时，对于枚举的第 i 个数和对应的答案集合，取集合中一半的数，把每个数询问 2^{i-1} 次，然后根据这一位为 0 还是 1 更新答案集合。

直接二分显然是过不去的，因此考虑优化。

首先我们发现当位置 a_i 的值确定后，所有剩余位置的值都不可能为 a_i，因此在确定 a_i 后可以同步更新剩余位置可能的取值。加上这步优化只需询问约 450 次。

然后是基于这点，我们发现每次应该尽可能询问最短的区间，因此每次询问时把所有区间从短到长排序。加上这步优化只需询问约 270 次，如果随机打乱询问位置只需询问约 259 次。

实测压到 2.5 n 可过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N=400;
using vi=basic_string<int>;

int i,j,k,n,m,t,li,res[N+50];

bitset<N+5> b[N+5],b0[N+5];

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void dfs(int x){
    if(res[x]||b[x].count()>1)return;
    int i,j,k;
    res[x]=b[x]._Find_first();
    for(i=1;i<=n;i++)if(i!=x&&b[i][res[x]]){
        b[i][res[x]]=0;
        dfs(i);
    }
}

bool chk(vector<pair<int,int> > v,int t1){
    reverse(v.begin(),v.end());
    int pw=1,k=0;
    for(auto [num,id]:v){
        t1-=pw*(num/2);
        if(t1<0)return 0;
        pw*=2;
    }
    return 1;
}

bool solve(){
    int i,j,k,pw=1,t1=li;

    vector<pair<int,int> > _v,v,Q;
    vector<pair<int,vi> > V;

    for(i=1;i<=n;i++)if(b[i].count()>1){
        _v.push_back({b[i].count(),i});
    }
    if(_v.empty())return 0;

    sort(_v.begin(),_v.end());

    for(auto p:_v){
        v.push_back(p);
        if(!chk(v,li)){
            v.pop_back();
            break;
        }
    }

    reverse(v.begin(),v.end());

    for(auto [num,id]:v){
        if(t1-pw*(num/2)<0)continue;
        basic_string<int> v1;
        for(j=1;j<=n;j++)if(b[id][j])v1+=j;
        shuffle(v1.begin(),v1.end(),rng);
        v1.resize(num/2);
        for(auto j:v1){
            for(int T=1;T<=pw;T++){
                Q.push_back({id,j});
                t1--;
            }
        }
        V.push_back({id,v1});
        pw*=2;
    }

    int msk=0;
    cout<<"? "<<Q.size()<<' '; for(auto [x,y]:Q)cout<<x<<' '<<y<<' '; cout<<endl; cin>>msk;

    for(auto [id,v]:V){
        k=msk%2; msk/=2;
        if(k){
            b[id].reset(); for(auto j:v)b[id][j]=1;
        }
        else{
            for(auto j:v)b[id][j]=0;
        }
    }
    for(i=1;i<=n;i++)dfs(i);
    return 1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n; 
    li=n*20;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)b[i][j]=1;
    }
    while(solve());
    cout<<"! "; for(i=1;i<=n;i++)cout<<res[i]<<' ';
    cout<<endl;
}