1. ARC070F - HonestOrUnkind
发现 \(a\leq b\) 时 \(b\) 内部可以构造出一个好人集合，一定无解；否则有两种情况：
- \(x\) 认为 \(y\) 是坏人，二者一好一坏，全部删去即可；
- \(x\) 认为 \(y\) 是好人，那么 \(y\) 一定比 \(x\) 更好。
维护一个栈表示目前越来越好的人，每次取出栈顶询问新人，若为好则将新人放入栈顶；否则将栈顶弹出。最后栈顶一定是一个好人，让他询问一遍所有人即可。
点击查看代码
//AT_arc070_d
#include <bits/stdc++.h>
using namespace std;
int qry(int x, int y){
if(x == y){
return 1;
}
printf("? %d %d\n", x, y);
fflush(stdout);
char s[4];
scanf("%s", s);
return s[0] == 'Y';
}
int st[4010];
int main(){
int n, a, b;
scanf("%d%d", &a, &b);
if(a <= b){
puts("Impossible");
fflush(stdout);
return 0;
}
n = a + b;
int tp = 0;
for(int i = 0; i < n; ++ i){
if(tp == 0){
st[++tp] = i;
} else {
if(qry(st[tp], i)){
st[++tp] = i;
} else {
-- tp;
}
}
}
int x = st[tp];
for(int i = 0; i < n; ++ i){
st[i] = qry(x, i);
}
putchar('!');
putchar(' ');
for(int i = 0; i < n; ++ i){
putchar(st[i] + '0');
}
puts("");
return 0;
}