Luogu

Gym

分析

我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。

规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。

假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。

考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus\{u,v\}|=\frac{n}{2}+2(1-|A\cap\{u,v\}|)$。那么每次可以确定一个二元组与 $A$ 的交是否 $=1$。

不妨令 $u=1$，那么可以得到其它的数是否可以同时和 $1$ 在 $A$ 内，这样子有两种可能的情况，都问一遍即可。

这里最坏会询问 $n+1$ 次，于是我们需要思考如何在 $499$ 次内找到一个 $I$。

考虑随机，那么一次问到一个 $\frac{n}{2}$ 的概率是 $\frac{{n\choose n/2}}{2^n}$，在 $n=1000$ 时约等于 $2.52\%$。于是随机 $499$ 次有很大的概率出解。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n,s[N],ans[N];

int query(int *s) {
    for (int i=1;i<=n;++i) putchar(s[i]+'0');
    puts(""),fflush(stdout);
    int res=read();
    if (res==n) exit(0);
    return res;
}

int main() {
    mt19937 rnd(time(0));
    n=read();
    while (1) {
        for (int i=1;i<=n;++i) s[i]=rnd()&1;
        if (query(s)==n/2) break;
    }
    for (int i=1;i<=n;++i) ans[i]=s[i];
    for (int i=2;i<=n;++i) {
        s[1]^=1,s[i]^=1;
        if (query(s)) ans[i]^=1;
        s[1]^=1,s[i]^=1;
    }
    query(ans);
    for (int i=1;i<=n;++i) ans[i]^=1;
    query(ans);
    return 0;
}