Solution
这题是博主写的第一道交互题，在此 mark 一下。
首先假设我们已经知道有若干蘑菇属于 A（或者 B），这里举例 A 的情况。构造
可以查询出序列中下划线里含有多少个 B，以及可以根据奇偶性知道 (x) 属于 A 或者 B。
然后每次不断扩大集合 A,B 的大小，精细求解极值可以得到操作次数 (sim 2sqrt n)。这样做大概有 80 pts。
发现在某些时刻下，使用
查询可以同时知道 (x)，(y) 属于 A 还是 B。在开始的时候使用这种查询，到达一个界 (Limit)，如果 (max{|A|,|B|}>Limit) 时使用上一种查询，两者结合后操作次数 (sim sqrt{3n})，可以得到 92 pts。（gjd的四名选手的得分）
前期查询相当于一次查询换得两个蘑菇的类型，求解极值的过程中发现如果提高效率（即一次查询换得更多的蘑菇类型），操作次数可以下降。
我们可以采取这样的方法使得 2 次查询换取 5 个蘑菇的类型。首先查询
根据奇偶性得到 (z) 的类型，剩余的根据其是否为 2 得到 (x e y) 或者 (x=y)。若为后者就赚了，因为有 1 换 3。否则再次查询
同样可以根据奇偶性得到 (v) 的类型。剩余的由于有 (x e y) 知道 (x) 和 (y) 合计贡献 0 或者 4，(u) 贡献 0 或 2。据此分辨出 (x)，(y)，(u) 的类型。这样 2 次操作得到 5 个蘑菇的类型。
期望下很优秀，但交互库是自适应的，发现最坏刚好卡满 226 次？精细调整 (Limit) 并且多次提交即可通过此题。
（题外话：开头使用一次 use_machine 一个打乱的序列可以避免被交互库自适应数据卡满。不过此做法无需使用）
当然还有使用 203 步解决问题的方法，详见 whzzt 的 codeforces blog。
#include "mushrooms.h"
#include <bits/stdc++.h>
#define pb push_back
using std::vector; using std::max; using std::min;
const int Limit = 116;
int ans = 0, now = 1;
vector<int> v[2], a;
int MaxSize() { return max(v[0].size(), v[1].size()); }
int count_mushrooms(int n) {
v[0].pb(0);
if (n > 1000) {
while (MaxSize() == 1)
v[use_machine(vector<int>{0, now})].push_back(now), now++;
while (MaxSize() == 2) {
int cur = v[0].size() < v[1].size(), tmp = use_machine(vector<int>{v[cur][0], now, v[cur][1], now+1});
v[cur ^ (tmp & 1)].pb(now + 1), v[cur ^ (tmp / 2)].pb(now); now += 2;
}
while (MaxSize() <= Limit) {
int cur = v[0].size() < v[1].size(), tmp = use_machine(vector<int>{v[cur][0], now, v[cur][1], now + 1, v[cur][2], now + 2});
v[cur ^ (tmp & 1)].pb(now + 2); tmp /= 2;
if (tmp % 2 == 0)
v[cur ^ (tmp / 2)].pb(now), v[cur ^ (tmp / 2)].pb(now + 1), now += 3;
else if (v[cur^1].size() < 2) {
tmp = use_machine(vector<int>{v[cur][0], now, v[cur][1], now + 3});
v[cur ^ (tmp & 1)].pb(now + 3); v[cur ^ (tmp / 2)].pb(now); v[cur ^ 1 ^ (tmp / 2)].pb(now + 1);
now += 4;
} else {
tmp = use_machine(vector<int>{v[cur^1][0], now, v[cur^1][1], v[cur][0], now + 1, v[cur][1], now + 3, v[cur][2], now + 4}) - 1;
v[cur ^ (tmp & 1)].pb(now + 4);
v[cur ^ (tmp / 2 & 1)].pb(now + 3);
v[cur ^ 1 ^ (tmp / 4 & 1)].pb(now);
v[cur ^ (tmp / 4 & 1)].pb(now + 1);
now += 5;
}
}
}
for (; now < n;) {
int cur = v[0].size() < v[1].size(), block = min((int)v[cur].size(), n - now);
a.clear(); a.pb(v[cur][0]);
for (int i = 0; i < block - 1; i++) a.pb(now + i), a.pb(v[cur][i + 1]);
a.pb(now + block - 1);
int tmp = use_machine(a);
v[cur ^ (tmp & 1)].pb(now + block - 1);
ans += cur ? tmp/2 : block - tmp/2 - 1;
now += block;
}
return ans + v[0].size();
}