有个数组\(a_i\in\{-1,0,1\}\)。你需要输出所有\(a_i=0\)的\(i\)。
交互。每次可以在这个数组的下标中选择两个不可相交的非空集合\(S,T\)，询问\(\sum_{x\in S}a_x\sum_{y\in T} a_y\)。
询问次数\(n+\lfloor\lg n\rfloor\)
\(n\le 2000\)
保证存在至少一个\(a_i=0\)，至少存在两个\(a_i\neq 0\)。
本来在想着算出\(x_i=query(\{a_i\},U \setminus \{a_i\})\)，然后后面进行一波分类讨论乱搞。感觉快行了但是剩下一种情况做不出来（\(\sum a_i\in \{1,-1\}\)时）。顺便提一下如果没有这种情况是\(n\)次的（手动滑稽）。
一开始把\(a_1\)丢入\(S\)中。然后从\(2\)开始做，先将\(a_i\)丢入\(T\)中问一下，如果问出了\(0\)则把\(a_i\)丢入\(S\)中；否则此时\(a_i\)一定非零，且\(S\)中的数的和也非零，因此此时\(a_i\)是第二个非零数。
于是在左边二分出第一个非零数，右边剩下的一个个判断。
次数\(n-1+\lceil \lg n\rceil\)。
using namespace std;
#include <bits/stdc++.h>
#define N 2005
int n;
vector<int> a,b;
int ask(){
printf("? %d %d\n",a.size(),b.size());
for (int i=0;i<a.size();++i) printf("%d ",a[i]);printf("\n");
for (int i=0;i<b.size();++i) printf("%d ",b[i]);printf("\n");
fflush(stdout);
int x;scanf("%d",&x);
return x;
}
int ans[N],cnt;
int main(){
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
cnt=0;
a.clear(),b.clear();
a.push_back(1);
for (int i=2;i<=n;++i){
b.push_back(i);
int x=ask();
if (!x){
b.pop_back();
a.push_back(i);
continue;
}
int l=1,r=i-1;
while (l<r){
int mid=l+r>>1;
a.clear();
for (int i=l;i<=mid;++i)
a.push_back(i);
x=ask();
if (x)
r=mid;
else
l=mid+1;
}
for (int j=1;j<i;++j)
if (j!=l)
ans[++cnt]=j;
for (int j=i+1;j<=n;++j){
a.clear();
a.push_back(j);
x=ask();
if (!x)
ans[++cnt]=j;
}
break;
}
printf("! %d ",cnt);
for (int i=1;i<=cnt;++i)
printf("%d ",ans[i]);
printf("\n");
fflush(stdout);
}
return 0;
}