Codeforces

分析

为了方便，下面把为 $y$ 的数称为特殊数。

首先我们可以通过一次询问得到某个集合内的特殊数的个数的奇偶性。

• 如果询问的集合大小是偶数，且特殊数的个数为偶数，那么返回值为 $0$ 。
• 如果询问的集合大小是偶数，且特殊数的个数为奇数，那么返回值为 $y$ 。
• 如果询问的集合大小是奇数，且特殊数的个数为偶数，那么返回值为 $x$ 。
• 如果询问的集合大小是奇数，且特殊数的个数为奇数，那么返回值为 $x\oplus y$ 。

因为 $0,x,y,x\oplus y$ 是互不相同的，所以很好判断奇偶性了。

我们从小到大枚举每个二进制位，然后把所有下标分成两组：这一位为 $1$ 的，这一位为 $0$ 的。

我们查询一下这一位为 $1$ 的下标的集合，如果特殊数的个数为奇数，那么两个特殊数的下标在该二进制位是不同的。

那么我们只需要至多 $10$ 次询问就可以得到两个特殊数的下标的异或值了，也就是说只要知道了一个就可以知道另一个。

然后我们把所有下标划分成两组，保证每组中各有一个特殊数。

那么只需要在其中一组中二分即可求出一个特殊数的下标。如果在小的那组中二分的话这一部分只需要至多 $9$ 次询问。

这样子就得到了一个特殊数的下标，再异或之前求出的那个东西就可以得到另一个特殊数的下标了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int query(vector<int> a) {
    if (!a.size()) return 0;
    cout<<"? "<<a.size();
    for (re int i:a) cout<<" "<<i;
    cout<<endl; fflush(stdout);
    int res; cin>>res; return res;
}

int main() {
    int n,x,y,diff=0,lbit; cin>>n>>x>>y;
    for (re int i=0;i<=9;++i) {
        vector<int> a; a.clear();
        for (re int j=1;j<=n;++j)
            if (j&(1<<i)) a.push_back(j);
        int res=query(a);
        if (res==y||res==(x^y)) diff|=(1<<i),lbit=i;
    }
    vector<int> a,b; a.clear(),b.clear();
    for (re int i=1;i<=n;++i) {
        if (i&(1<<lbit)) a.push_back(i);
        else b.push_back(i);
    }
    if (a.size()>b.size()) swap(a,b);
    int L=0,R=a.size()-1;
    while (L<R) {
        int mid=(L+R)>>1;
        vector<int> c; c.clear();
        for (re int i=L;i<=mid;++i) c.push_back(a[i]);
        int res=query(c);
        if (res==y||res==(x^y)) R=mid;
        else L=mid+1;
    }
    int ans1=a[L],ans2=ans1^diff; if (ans1>ans2) swap(ans1,ans2);
    cout<<"! "<<ans1<<" "<<ans2<<endl; fflush(stdout);
    return 0;
}