题解：AT_arc070_d [ARC070F] HonestOrUnkind

牛逼构造，硬控我 2h。

一些注释：

1.身份高/低：身份高指好人面大，身份低指好人面小，可以理解为好人权值为 1 ，坏人权值为 0 。

2.同底色：身份相同，同为好人或坏人。

找到一个好人然后 n-1 次操作即可得到答案，考虑如何用 n+1 次操作内找到这个好人。

考虑当 a \leq \frac{n}{2} 时一定无解，因为可以在 b 个坏人中选出 a 个假扮好人，我们无法区分；当 a > \frac{n}{2} 时，考虑 O(n^2) 做法，若 u 认为 v 是好人，就连边 u \to v ，大小大于 \frac{n}{2} 的强连通分量就是好人集合，其他都是坏人。

考虑这么做为什么是对的。经常玩狼人杀的小朋友们应该知道一个结论：若 u 认为 v 是好人，那么 u 的身份不会高于 v 。

证明如下：若 u 是坏，那么 v 身份不会比他更低；若 u 是好，而他认为 v 是好，那 v 的确是好。

那么我们刚刚所找的一个强连通分量也就意味着一些同底色的人，由于好人策略固定，所以好人一定在一个强连通分量，而坏人不能在。怎么找到这个强连通分量呢？就是那个最大的强连通分量！因为大小等于 a 的强连通分量只有一个，且一定是最大的。

这个 O(n^2) 的做法很复杂，但是他给我们一个很厉害的定理，可是这个做法无法拓展的主要原因是没有利用上坏人判定。

经常玩狼人杀的小朋友们应该又知道一个结论：若 u 认为 v 是坏，那么 u 与 v 至少有一个是坏人。

在狼人杀中这是一般情况，但是在这道题中是一定正确的，因为两个好人不会互相判定为坏人。

一个很妙的 Trick 就是每次抓到一对 (u,v) 满足 u 认为 v 是坏人，把他们都删掉，删到不能删为止，剩下的人一定是好人，因为好人数量 > \frac{n}{2} ，而一次最劣也是一个好人换一个坏人。

精彩的部分来了，我们将上述两个定理结合，维护一个内向森林，一条边 x \to f 指 x 的身份比 f 低，也就是 x 认为 f 是好人，那么树根就是树里身份最高的人。

每次找两个树根 u,v ，若 u 认为 v 是好人，那么连边 u \to v ，可以将两棵树合并；若 u 认为 v 是坏人，那么 u,v 中至少有一个是坏人，树根是坏人那整棵树都是坏人（因为树根就是树里身份最高的人），所以两棵树中至少有一棵树全是坏人（全员恶人），那么每次同时删两棵树的叶子直到一棵树空，这样每次删的一对至少有一个是坏人，剩下的人就一定是好人。

如上两种操作都至少让树的数量减少一，那么至多做 n-1 次操作，也就是在 2n-2 次操作内做完了这道题！

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=4e3+10;
int n,a,b,rt,vis[N];
vector<int> G[N];
struct FaC{
    int fa[N],sz[N];
    void init(){for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;}
    int find(int x){return (fa[x]==x?x:fa[x]=find(fa[x]));}
    void merge(int x,int y){
        x=find(x),y=find(y);
        fa[x]=y,sz[y]+=sz[x];
    }
    int size(int u){return sz[u];}
}F;
int ask(int x,int y){
    cout<<"? "<<x-1<<' '<<y-1<<endl;
    char s;
    cin>>s;
    return (s=='Y');
}
void del(int x){
    for(int y:G[x]) if(!vis[y]){
        del(y);
        return ;
    }
    vis[x]=1;
    return ;
}
int main(){
    // ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    // freopen("nzq.in","r",stdin);
    // freopen("nzq.out","w",stdout);
    cin>>a>>b;
    if(a<=b){
        cout<<"Impossible"<<endl;
        return 0;
    }
    n=a+b;
    F.init();
    for(int c=1;c<n;c++){
        int u=-1,v=-1;
        for(int i=1;i<=n;i++) if(!vis[i] && F.find(i)==i){
            if(u==-1) u=i;
            else v=i;
        }
        if(v==-1) break;
        int op=ask(u,v);    
        if(op==1){
            F.merge(u,v);
            G[v].push_back(u);
        }else{
            for(int j=1;j<=min(F.size(u),F.size(v));j++){
                del(u),del(v);
            }
        }
    }
    for(int i=1;i<=n;i++) if(!vis[i]) rt=i;
    string s="";
    for(int i=1;i<=n;i++){
        if(rt==i) s=s+'1';
        else s=s+(char)(ask(rt,i)+'0');
    }
    cout<<"! "<<s<<endl;
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}