Problem

AtCoder

Luogu

Solution

对于这道题，交互类型，可能有些生疏，但是细看还是可做的。

好人就会说真话，而坏人视情况说，即他说的话你无法全信。

首先考虑什么时候无解，显然当 a \leq b 的时候就无解了，因为这个时候 b 个坏人中的 a 个人是可以假装那 a 个好人的，他们互相指认为好人并且把其他人都指认为坏人，你就永远无法分辨出他们和真正的好人。

然后考虑 a>b，我们的思路是在保持 a>b 的性质不变的情况下将 n 的规模缩小，同时均摊下来每两次查询确定一个人，我们可以基于这样的一个策略：

显然我们可以先找出来一个好人，然后由他来得到其他人的身份。

这样来说我们怎么让好人可以快速指认好人呢？

两两互相指认么？

貌似这样我们需要 3 \times n 的次数。

我们尝试一下，对一个询问进行剖析： ? x y

如果 x 指认 y 是好人，如果 x 是好人，那么 y 也是好人，如果 x 是坏人，那么 y 的身份无法确认。

如果 x 指认 y 是坏人，那么非常清楚，x 和 y 中必然至少有一个人是坏人，x 是好人的话，y 就是坏人，x 是坏人的话，那就是坏人！

考虑到 a > b 这一性质，所以我们可以暴力一点，找好人的时候可以连坐杀人（

怎么找呢？维护一个数据结构。

能做到这样的，我找一个人问另外一个人，另外一个人问另另外一个人。

然后存在 指认坏人 的情况的，两个人都不考虑成为最后人选，最好是这个最后人选应该是最优的答案。

那么因为 a > b 我们同时删去 k 人，仍能保持 a > b。

所以在我们捏造的这个链上，只存在 指认为好人的情况，即使前面都是坏人，只要有一个节点出现好人，那么之后的节点只会是好人。

嗯，然后最后一个节点就是最后人选，拿他去问 n 次就可以了。

这个数据结构是什么呢？其实用什么无所谓（（（

我选择用栈。

维护一个栈，依次扫过每个点，如果栈为空就把它入栈，否则询问栈顶这个人是不是好人。

如果是，就是入栈，如果不是，就弹栈（刚刚扫过的节点都没入栈呢）。

Code

#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

char s[10];

void query(int x, int y)
{
    printf("? %d %d\n", x, y);
    fflush(stdout);
    scanf("%s", s);
}
int flag[6020];
stack<int> q;

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    if (a <= b)
    {
        printf("Impossible\n");
        return 0;
    }
    int n = a + b;
    for (int i = 0; i < n; i++)
    {
        if (q.empty())
        {
            q.push(i);
            continue;
        }
        query(q.top(), i);
        if (s[0] == 'Y') q.push(i);
        else q.pop();
    }
    for (int i = 0; i < n; i++)
    {
        query(q.top(), i);
        if (s[0] == 'Y') flag[i] = 1;
    }
    printf("! ");
    for (int i = 0; i < n; i++) printf("%d", flag[i]);
    puts("");
    fflush(stdout);
    return 0;
}