交互、贪心、二分

发现这个询问只能鉴定是否 $S_1,S_2$ 都有金苹果。

考虑按位询问，每次询问编号第 $i$ 位为 $0$ 的所有苹果和第 $i$ 位为 $1$ 的所有苹果，这样能通过至多 $10$ 次询问得到两个金苹果编号的异或和。

接下来找到异或和一个为 $1$ 的位（显然由于两个金苹果编号不同所以必定有一个位是 $1$），这一位为 $0$ 的所有苹果里肯定有一个金苹果，可以使用这个金苹果鉴定一个集合里是不是有金苹果。每次鉴定一半的可疑苹果可以排除掉一半的可疑苹果，最后剩余的可疑苹果就是金苹果。

由于某一位为 $1$ 的金苹果至多有 $512$ 个，不超过 $9$ 次询问就可以得到金苹果的编号，异或得到另一个金苹果编号。询问次数最多为 $19$ 次，可以通过本题。

#include<bits/stdc++.h>
using namespace std;
int ask(set<int> s){
    static int ret;
    printf("? %u",s.size());
    for(int i:s) printf(" %d",i);
    putchar('\n');
    fflush(stdout);
    scanf("%d",&ret);
    return ret;
}
void solution(){
    int n=0,w=0,sum=0,ans=0;
    scanf("%d",&n);
    for(int i=0;(1<<i)<=n;i++){
        set<int> s;
        for(int j=1;j<=n;j++) if((j>>i)&1) s.emplace(j);
        if(ask(s)) w=i,sum|=1<<i;
    }
    set<int> res;
    for(int i=1;i<=n;i++) if((i>>w)&1) res.emplace(i);
    while(res.size()>1u){
        set<int> s[2];
        int x=0;
        for(int i:res) s[x^=1].emplace(i);
        res=s[ask(s[1])];
    }
    ans=*res.begin();
    if(ans>(ans^sum)) ans^=sum;
    printf("! %d %d\n",ans,ans^sum);
    fflush(stdout);
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}