AtCoder Regular Contest 070F：Honest Or Unkind

题目传送门：https://arc070.contest.atcoder.jp/tasks/arc070_d

题目翻译

有(n)个人，其中有(a)个人是诚实的，另外(b)个是不诚实的。你可以向交互库提问：如果问(x)号(y)号是否诚实(x)将怎么回答？如果(x)是诚实的，那么(x)的回答就是正确的，否则有(50)%的几率是他瞎扯淡来唬你的。你的提问次数不能超过(2n)次，请确定哪些人是诚实的，哪些不是。如果为无法确定，那么输出Impossible。(a,bleqslant 2000)

题解

如果(aleqslant b)那么就确认不了，我只需要从(b)个骗子里叫(a)个说真话你就(GG)了。

当(a>b)我们就可以确认，只需要找出一个诚实的人，然后问他这(n)个人分别是不是诚实的就行了。假设存在一条链(x_1->x_2->x_3->...->x_k)，表示(x_{i-1})说(x_i)是诚实的。这(k)个人里面只要任意一个人是诚实的，那么(x_k)就必然是诚实的。所以我们可以维护一个栈，如果栈顶说当前枚举的人不是真的，那么两个人里面必然有一个假的，那我两个都不要。因为(b>a)所以最后栈里必然会留下一些人并且这些人中肯定有诚实的人，栈顶必然是诚实的，我们再问栈顶的人(n)个问题就解决了。

时间复杂度：(O(n))

空间复杂度：(O(n))

代码如下：

#include <cstdio>
using namespace std;
 
const int maxn=4005;
 
int n,a,b,top;
int sta[maxn];
bool ans[maxn];
 
int read() {
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x*f;
}
 
int main() {
	a=read(),b=read(),n=a+b;
	if(a<=b) {puts("Impossible");return 0;}
	for(int i=1;i<=n;i++)
		if(!top)sta[++top]=i;
		else {
			printf("? %d %d
",sta[top]-1,i-1);
			fflush(stdout);char s[3];
			scanf("%s",s+1);
			if(s[1]=='N')top--;
			else sta[++top]=i;
		}
	int honest=sta[top];
	for(int i=1;i<=n;i++) {
		printf("? %d %d
",honest-1,i-1);
		fflush(stdout);char s[3];
		scanf("%s",s+1);
		ans[i]=(s[1]=='Y');
	}printf("! ");
	for(int i=1;i<=n;i++)
		printf("%d",ans[i]);
	return 0;
}