P14828 彻彻崩 题解

· · 题解

思路

考虑二分。对于每个数字，二分它出现在数组的 [l,mid] 位置还是 [mid+1,r] 位置。这样一个数字二分 \mathcal O(\log n) 次即能找到位置。

注意到询问长度可以达到 20n。因此我们可以同时询问 \lfloor\log_220\rfloor 个数字。

这样可以直接获得 72 分。

注意到二分到后面，区间变短，询问长度会越来越短，剩余的浪费很可惜。于是我们考虑压榨这些，同时询问后面的数字。

注意不要忘记把已经确定数字的位置，从其他没二分完的数字的候选列表中删掉。

这样就有 82 分 了。（赛时这里写的有点问题，应该有 86 分的。）

同时询问多个数字时，我们使用 2 的幂来区分各个数字，而数字较多时，肉眼可见地浪费。因此我们改变顺序，优先询问区间较长的数字。获得 91 分。

没辙了么？我们引入玄学，既不从短到长，也不从长到短，而是随机打乱。直接通过。

非常恐怖，询问长度压到 7n 都能过。

实现

#include<stdio.h>
#include<vector>
#include<algorithm>
#define pr pair<int,int> 
using namespace std;
int n,ans[409];
main()
{
    scanf("%d",&n);
    vector<vector<int> >cand(n+1);
    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)cand[i].emplace_back(j);
    for(;;)
    {
        vector<pr>ord;
        for(int i=1;i<=n;++i)if(cand[i].size()>1)
            ord.emplace_back(cand[i].size(),i);
        if(!ord.size())break;
        random_shuffle(ord.begin(),ord.end());
        vector<pr>q;
        for(int i=0,id=1,sz=0;i<ord.size();++i)
            if(sz+id*(cand[ord[i].second].size()>>1)<=20*n)
        {
            vector<int>&tmp=cand[ord[i].second];
            int mid=tmp.size()>>1;
            for(int j=0;j<mid;++j)for(int k=id;k--;)
                q.emplace_back(tmp[j],ord[i].second);
            sz+=id*mid;id<<=1;
        }
        printf("? %d ",q.size());
        for(int i=0;i<q.size();++i)printf("%d %d ",q[i].first,q[i].second);
        putchar('\n');fflush(stdout);
        int x;scanf("%d",&x);
        vector<int>del;
        for(int i=0,id=1,sz=0;i<ord.size();++i)
            if(sz+id*(cand[ord[i].second].size()>>1)<=20*n)
        {
            vector<int>&tmp=cand[ord[i].second];
            int mid=tmp.size()>>1;
            if(x&id)tmp.resize(mid);
            else for(int o=mid;o--;tmp.erase(tmp.begin()));
            if(tmp.size()==1)del.emplace_back(tmp[0]);
            sz+=id*mid;id<<=1;
        }
        for(int i=1;i<=n;++i)if(cand[i].size()>1)for(int j:del)
        {
            int k=lower_bound(cand[i].begin(),cand[i].end(),j)-cand[i].begin();
            if(k<cand[i].size())if(cand[i][k]==j)
                cand[i].erase(cand[i].begin()+k);
        }
    }
    for(int i=1;i<=n;++i)ans[cand[i][0]]=i;
    printf("! ");for(int i=1;i<=n;printf("%d ",ans[i++]));
}