【AtCoder Regular Contest 070 F】HonestOrUnkind | Mrsrz's blog

贪心，构造。

题目大意：

交互题。

有 $n$ 个人，标号 $0\sim n-1$，其中有 $A$ 个诚实的人和 $B$ 个不诚实的人，他们互相知道每个人是否诚实。

你可以进行不超过 $2n$ 次提问，格式为 ? a b，表示问 $a$ 号人 $b$ 号人是否诚实。若 $a$ 诚实，则他会如实回答。若 $a$ 不诚实，则他有可能说假话。

最后输出每个人是否诚实。

如果无法问出来，输出 Impossible。

题解：

若 $A\leq B$，则是无解的。因为那 $B$ 个人总有方法串通起来，让你无法判断出某个人是不是诚实的。

考虑 $A\gt B$ 的情况，我们如果知道了一个人是诚实的，那么问他所有人的情况即可。

我们考虑构造一种方案，使得能在 $n$ 次询问下确定一个诚实的人。

考虑用一个栈来维护，每次加入一个人，若栈不为空，则询问栈顶的人，这个新来的人的情况。若回答不诚实，则这两个人中至少有一个人不诚实，弹出栈顶并丢掉新来的。如果回答诚实，则将其加入栈中。

我们考察最后栈的情况，一定是栈底若干个不诚实的（可能没有），栈顶若干个诚实的（一定有）。上面不可能出现不诚实的，因为诚实的一定会披露不诚实的。而一次删除，最坏情况会删掉一个诚实的，一个不诚实的。由于诚实的人多，最后一定会留下至少一个诚实的。那么栈顶的就是诚实的。

接着问栈顶的人所有人的情况即可。

Code：

#include<cstdio>
int A,B,sta[4333],n,top,x;
char s[7],t[4333];
int main(){
    scanf("%d%d",&A,&B),n=A+B;
    if(A<=B)return puts("Impossible"),0;
    for(int i=0;i<n;++i)if(!top)sta[++top]=i;else{
        printf("? %d %d\n",sta[top],i),fflush(stdout),scanf("%s",s);
        if(*s=='Y')sta[++top]=i;else--top;
    }
    x=sta[top],t[x]='1';
    for(int i=0;i<n;++i)if(i!=x){
        printf("? %d %d\n",x,i),fflush(stdout),scanf("%s",s);
        t[i]=(*s=='Y')+48;
    }
    printf("! %s\n",t);
    return 0;
}