[EGOI 2021] Twin Cookies / 姐妹分饼干

Tairitempest · 2025-05-09 14:39:18 · 题解

[EGOI 2021] Twin Cookies

本题无需随机化，甚至在 15 次查询内可以通过。

随机配送饼干，选出一些分成两组，他们美味值总和相等。考虑到每次配送饼干是随机的，我们需要让某一次配送饼干的时候所有的选项都可以让它们选出一些分成两组，他们美味值总和相等。

为了方便构造，我们可以让一组只有一个，通过其他的饼干美味值拼凑出一个符合条件的美味值集合，至少有 N 个元素。因为 N \leq 5000，因此至少只需要 13 块饼干就能得到一个这样的饼干集合。

稳定通过的实现方法

为了保证可以稳定通过，需要保证任意饼干子集的美味值总和互不相同。通过保证每次选取的饼干美味值都大于以前获得的所有饼干的美味值总和，本次饼干贡献的所有美味值子集总和不会和以前的饼干贡献的所有美味值子集总和有任何交错。

最后拼凑出来的结果很有可能是某个饼干已经询问过的结果。考虑让美味值最小的饼干，其美味值也大于 N，然后获取一个美味值极大的饼干（本人使用了 10^{15}+i,1 \leq i \leq N）。这样的话我们可以保证美味值极大的饼干贡献的所有美味值子集总和都大于 10^{15}+N，自然这些饼干我们是没有询问过的。

因此我们可以在合法的时间复杂度和 15 次询问内解决问题。

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

vector<ll> seletc;
vector<ll> out;
vector< array<ll,2> > oknum;
ll n,pos,mv,ans,anspos;

int main(){
    cin>>n;
    pos=n+1;
    for(ll _=0;_<13;_++){
        cout<<'?';
        for(ll __=n;__>0;__--){
            cout<<' ';
            pos++;
            cout<<pos;
        }
        cout<<endl;
        ll tmp;
        cin>>tmp;
        seletc.push_back(tmp);
        pos<<=1;
        pos+=n;
    }
    oknum.push_back({0,0});
    for(ll i=0;i<13;i++)
        for(ll k=0;k<(1<<i);k++)
            oknum.push_back({oknum[k][0]+seletc[i],oknum[k][1]+(1<<i)});
    cout<<'?';
    for(ll i=1;i<=n;i++)
        cout<<' '<<i+(ll)(1e15);
    cout<<endl;
    cin>>mv;
    cout<<'?';
    for(ll i=1;i<=n;i++)
        cout<<' '<<mv+oknum[i][0];
    cout<<endl;
    cin>>ans;
    for(ll i=1;i<=n;i++)
        if(ans-mv==oknum[i][0]) anspos=i;
    ll msk=oknum[anspos][1];
    for(ll k=0;k<13;k++){
        if(msk%2==1) out.push_back(seletc[k]);
        msk/=2;
    }
    cout<<"! 1 "<<out.size()+1<<endl<<ans<<endl<<mv;
    for(ll i:out){
        cout<<' '<<i;
    }
    cout<<endl;
    return 0;
}