【题解】 CF1466I The Riddle of the Sphinx
神仙交互题......
题意：
已知现有一个长 $n$ 的数组，每个数字都是严格小于 $2^b$ 的非负整数，每次可以给定 $i,x$ 来询问 $a_i>x$ 是否成立。
需要在 $3\times(n+b)$ 次询问之内求出数组的最大值。
$n,k\le 200$，交互库自适应。
（本题解思路来自官方 $\text{Tutorial}$）
提前约定
以下所述的“前缀”均指一个二进制数从高位到低位的一部分，一个元素的前 $k$ 位表示二进制从高位到低位的前 $k$ 位。
接下来会有很多地方需要判断一个位置的元素的前 $k$ 位与另一个数字 $x$ 前 $k$ 位的大小关系，这可以通过将 $x$ 的前 $k$ 位保留，后面补 $0$ 或 $1$ 来求出。
稍劣解法
考虑一个稍微劣的做法，可以在 $5\times (n+b)$ 次询问之内求出答案。
由于位数较大，因此我们希望从高位到低位确定最大值的每一位。从 $1$ 到 $n$ 依次考虑每一个元素，同时维护一个栈，栈中保留一些元素，并求当前已经求出的最大前缀。
具体来说，该栈需要满足这样的条件：
- 栈中元素个数 $=$ 当前保留的最大前缀长度。
- 栈中自底向上第 $k$ 个元素的二进制前 $k$ 位 与 当前保留的最大前缀的前 $k$ 位相同。
再考虑加入元素 $i$ 进行的操作，若当前栈中有 $m\ (m<b)$ 个元素（同时确定的最大前缀有 $m$ 位）：
- 若 $i$ 的前 $m$ 位大于当前确定的最大前缀，则弹出栈顶，将最大前缀的最后一位删除，再重新考虑同样的步骤。
- 若 $i$ 的前 $m$ 位等于当前确定的最大前缀，则确定 $i$ 元素的第 $m+1$ 位，将 $i$ 加入栈中，同时更新最大前缀的 $m+1$ 位为元素 $i$ 的第 $m+1$ 位。
- 若 $i$ 的前 $m$ 位小于当前确定的最大前缀，则跳过该元素。
考虑完所有元素之后，若栈中仍然存有 $m$ 个元素（同时有一个长度为 $m$ 的前缀），那么我们认为现在的前缀可能是最大的前缀。
为什么是可能？我们发现，上述算法中的每一个元素，对最大前缀的贡献最多只有一位。有可能某一个元素十分大，却只有一位被加入了贡献，这是十分不划算的。
例如栈中元素为：
$$ 10\red{1}0 $$
$$ 1\red{0}01 $$
$$ \red{1}111 $$
那么我们确定的前缀是 $101$，然而，最下面的元素有一个更大的前缀：$111$。
因此，现在需要做的是处理这样的情况，就算缩短确定的最大前缀长度，也要保证当前的前缀一定是最大的。
那么自栈顶向下考虑，若现在的最大前缀长度为 $m$ ：
- 若栈顶元素 $i$ 的前 $m$ 位小于等于最大前缀，那么直接弹出这个元素。
- 若栈顶元素 $i$ 的前 $m$ 位大于最大前缀，那么说明当前的最大前缀是假的，只有最大前缀的前 $i$ 位是暂时仍然正确的。那么，将最大前缀删至长度为 $i$，弹出 $i$ 上方所有的元素。
这样处理之后，我们发现虽然最大前缀变短了，但是由于每一个元素都再一次与最大前缀进行比较，因此这个最大前缀就一定是真的了。
假设最大前缀长度为 $k$，那么相当于我们已经确定了答案的前 $k$ 位。因此接下来，直接递归处理即可。
为了进行递归，我们需要找出所有前 $k$ 位恰好等于最大前缀的元素，只有他们才有可能成为最大值。因此还需要再对每一个数字扫一遍，保留满足上述条件的位置，再进行递归处理。
分析次数
分析一下上述做法为什么是 $5\times (n+b)$ 的。
第一次对整个数组进行考虑时，扫描每一个位置，若选择将一个位置加入，则需要 $3$ 次询问；若选择弹出栈顶，则需要 $1$ 次询问；从栈顶向下考虑，每一个值都需要 $1$ 次询问；寻找前缀与最大前缀相同的位置，每一个位置都需要 $1$ 次询问。
因此第一次对整个数组进行扫描时，需要 $5n$ 次询问左右。
再考虑递归的情况。可以证明，当我们在一轮中确定了一个长度为 $k$ 的最大前缀，则与之匹配的位置至多只有 $k$ 个。
那么我们会在答案中填上 $k$ 位，同时下一轮只会花费 $5k$ 次操作。
由于答案长度为 $b$，所以很好证明之后所有轮数加起来只会花费 $5b$ 次询问。因此该做法可以在 $5\times(n+b)$ 次询问内求出最大值。
考虑优化
想想上面的做法有哪里是浪费的。首先十分显然的，后面寻找哪些位置的前缀与最大前缀匹配的步骤都是浪费的——因为只有栈中最后留下的元素满足这个条件。
因此只需要将这些栈中留下的元素取出来进行递归即可。询问次数降低为 $4\times(n+b)$。
但是还是不够。发现上面我们在扫描每一个位置，考虑加入栈中的时候，对于一个元素进行 $3$ 次询问实在是太亏了。
判断大于的一次询问肯定是无法省去的，因为我们需要他来判断是否需要弹出栈顶。
但是，判断等于和小于的两次，我们是否可以将他们合并为一次呢？当我们放宽一些要求，不要求栈中元素的前缀与最大前缀的前缀相同，而是变成这样的要求：
- 栈中自底向上第 $k$ 个元素的前 $k$ 位不能大于最大前缀的前 $k$ 位。
- 栈中至少有一个元素，满足其 $\ge$ 最大前缀。
发现如果要求变成这样，就不需要判断是否小于了，而是直接确定位数并加入栈中。
至于继续维护他的正确性，我们发现在第二步自顶向下弹栈的时候，如果一个元素本来在加入时就小于当时的最大前缀，那么他一定会被弹掉！因此正确性就被保证了。
这样，我们就不需要判断小于或等于，而是直接判断该元素某一位是 $0$ 还是 $1$。这样就将询问次数变为 $3\times(n+b)$，可以通过。
$\text{Code:}$
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define LINE() cout << "LINE = " << __LINE__ << endl
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define vec vector
const int MAXN = 210;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, b;
char s[5];
bool res;
vec<int> now;
string ans, opt;
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
a *= f;
return 1;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
void print(int pos, string now, int op) {
res = 0;
cout << pos << ' ' << ans << now;
for(int i = ans.length() + now.size(); i < b; ++i) putchar(op + '0');
cout << endl;
cin >> opt;
res = (opt[0] == 'y');
}
void solve(vec<int> id) {
if(ans.size() == b) return;
if(!id.size()) {
int lim = ans.size();
for(int i = lim + 1; i <= b; ++i) ans = ans + "0";
return;
}
vec<int> stk(0);
string cur = "";
print(id[0], "0", 1);
cur += (res ? "1" : "0");
stk.pb(id[0]);
for(int i = 1, p, ok; i < id.size(); ++i) {
p = id[i], ok = false;
print(p, cur, 1);
if(res) ok = true;
while(stk.size() && res) {
cur.pop_back();
stk.pop_back();
print(p, cur, 1);
}
if(ans.size() + cur.size() == b) continue;
res = false;
if(!ok) print(p, cur + "0", 1);
if(ok || res) cur += "1";
else cur += "0";
stk.pb(p);
}
for(int i = stk.size() - 1; ~i; --i) {
print(stk[i], cur, 1);
if(res) {
while(stk.size() > i + 1) {
stk.pop_back();
cur.pop_back();
}
}
}
ans += cur;
solve(stk);
}
signed main () {
#ifdef FILE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(n), read(b);
for(int i = 1; i <= n; ++i) now.pb(i);
solve(now);
cout << 0 << ' ' << ans << endl;
return 0;
}