【Solution】The penguin's game

xcrr · 2023-08-12 17:29:31 · 题解

好题好题

看到 19，不禁想到询问次数可能是 2\cdot \log。

假设那两个冰柱分别是 Y_1,Y_2，其余冰柱是 X。

于是我一眼想二分。然而因为两个 Y 都在原集合里，没办法做。如果只有一个 Y 在集合里就好办了。

于是想怎么把两个 Y 拆到两个集合。考虑经典的 \log 复杂度内拆集合，使得任意两个数都至少有一次在不同集合的方法：每次对二进制每一位拆，这位为 1 去左边集合，0 去右边集合。

而且我们可以判断一个集合内是否有奇数个 Y，即异或值为 y（集合大小为奇数）或者 x+y（集合大小为偶数）。

初步做法出来了，\log 次拆集合，每次询问其中一个，如果有奇数个 Y，那么就拆分成功了。

这时候可以在集合内二分了。但是如果给两个集合都做二分，总共询问是 3\cdot \log 次。考虑只给一个集合二分，求出 Y_1。因为前面拆集合的操作可以确定 Y_1 和 Y_2 在每位上是否相同，合在一起可以确定 Y_1 \oplus Y_2，所以我们可以求出 Y_2。

没有细节，上代码。

//沉着冷静
int n,x,y;
int fd(vector<int>t)
{
    int sz=t.size();
    vector<int>now;
    now.push_back(-1);
    for(auto c:t)now.push_back(c);
    int sum=0;
    for(int i=(1<<9);i;i>>=1)
    {
        if(sum+i>sz)continue;
        cout<<"? "<<sum+i<<' ';
        for(int j=1;j<=sum+i;j++)
        cout<<now[j]<<' ';
        cout<<endl;
        fflush(stdout);
        int p;
        cin>>p;
        if((((sum+i)&1)&&p==y)||(!((sum+i)&1)&&p==(x^y)));
        else sum+=i;
    }
    return now[sum+1];
}
inline void solve(){
    cin>>n>>x>>y;
    int w=0,a=-1;
    vector<int>st;
    for(int i=0;i<=9;i++)
    {
        st.clear();
        for(int j=1;j<=n;j++)
        if((j>>i)&1)st.push_back(j);
        if(!st.size())continue;
        cout<<"? "<<st.size()<<' ';
        for(auto c:st)cout<<c<<' ';
        cout<<endl;
        fflush(stdout);
        int p;
        cin>>p;
        if(((st.size()&1)&&p==y)||(!(st.size()&1)&&p==(x^y)))
        {
            if(a==-1)a=fd(st);
            w^=(1<<i);
        }
    }
    int b=a^w;
    if(a>b)swap(a,b);
    cout<<"! "<<a<<' '<<b<<endl;
    fflush(stdout);
}