考虑当$ale b$时，构造两种方案，满足诚实的人不交，接下来要求对于任意询问，这两种方案的答案都有可能相同
考虑询问$(i,j)$，若$i$在两种方案中有一种不诚实，那么总可以让答案相同，又因为诚实的人不交，因此一定可行
当$a>b$，我们只需要找到一个诚实的人就可以做了，考虑如何找到这个诚实的人：
对于询问$(i,j)$，若结果为不诚实，至少存在一个人不诚实，考虑同时删去$i$和$j$，显然最终不可能只剩下不诚实的人
维护一个栈（初始为空），从1到$n$遍历所有人，并询问$(栈顶,i)$，考虑结果：
1.结果为不诚实，同时删去（弹出）栈顶和$i$即可
2.结果为诚实，将$i$加入栈中，并继续此过程
当我们询问完之后，可以发现栈中若栈顶不诚实，由于栈顶的下一个元素认为栈顶诚实，因此其也不诚实，以此类推，整个栈中所有人都不诚实，即矛盾
通过栈顶再$n$次询问即可确定剩余的人
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 4005 4 stack<int>st; 5 int a,b,ans[N]; 6 char s[11]; 7 int query(int x,int y){ 8 printf("? %d %d ",x-1,y-1); 9 fflush(stdout); 10 scanf("%s",s); 11 return s[0]=='Y'; 12 } 13 int main(){ 14 scanf("%d%d",&a,&b); 15 if (a<=b){ 16 printf("Impossible"); 17 return 0; 18 } 19 for(int i=1;i<=a+b;i++) 20 if (st.empty())st.push(i); 21 else{ 22 if (query(st.top(),i))st.push(i); 23 else st.pop(); 24 } 25 for(int i=1;i<=a+b;i++)ans[i]=query(st.top(),i); 26 printf("! "); 27 for(int i=1;i<=a+b;i++)printf("%d",ans[i]); 28 }