日本师傅出的题还是比较滴有思维含量，同学们要认真学习，就是这个交互勒格式不太规范哈！

题意

有 $n$ 种钥匙，每种钥匙有 $m$ 个，一开始每把钥匙的种类未知。一位大师傅要撇 $m$ 串钥匙，每串上面都有 $n$ 个种类不同的钥匙。他有一个机器，给这个机器一个钥匙集合，机器可以返回这个集合最多可以串多少串钥匙，要求在使用不超过 $50000$ 次机器的情况下串好钥匙。$n\le 10^4,m\le 25$

题解

经典的钥匙-锁模型的咩。考虑暴力坐板凳囊个坐，我们依次枚举每把钥匙，再枚举每个串，判断这把钥匙是否能挂到这个串上。容易发现，如果把除了这串上已经有的钥匙以及当前枚举的钥匙之外的所有钥匙都放进机器里面问一哈，如果结果 $\ge n-1$ 就证明这把钥匙可以挂到这一串上。

但是这个俎法要 $nm^2$ 次询问，超限了撒。考虑 $50000$ 大概是 $nm\log m$ 的样子，套路的想到了二分。设 $S$ 是当前可能的钥匙串的集合，怎么判断能不能把钥匙 $x$ 放到这个集合内呢？我们还是按照之前的方法，把除了 $x$ 和在 $S$ 中的钥匙之外的所有钥匙放到一起问一遍，如果结果 $\ge n-|S|$ 就证明 $S$ 中可以放。我们每次将可能的集合分成两半，选择一边判断，最后就可以用 $\log m$ 的代价找到一个合法的钥匙串了咩！

#include <vector>
using namespace std;
int Query(const std::vector<int> &x);
void Answer(const std::vector<int> &a);
vector<int>keys[35];
bool seat[10005];
bool check(int N,int M,int l,int r,int k)
{
for (int i=1;i<=N*M;++i) seat[i]=0;
 for (int i=l;i<=r;++i)
  for (int j:keys[i]) seat[j]=1;
 vector<int>ask;
 	seat[k]=1;
 for (int i=1;i<=N*M;++i)
 if (!seat[i]) ask.push_back(i);
 return Query(ask)>=M-(r-l+1);
}
int sit(int N,int M,int x) {
  int l=1,r=M,mid;
   while (l<r)
    {
	mid=(l+r)/2;
  if (check(N,M,l,mid,x)) r=mid;
	else l=mid + 1; 
  } return l;
}
void Solve(int N,int M){
  for (int i=1;i<=M;++i)keys[i].push_back(i);
 for (int i=M+1;i<=N*M;++i)
	keys[sit(N,M,i)].push_back(i);
  for (int i=1;i<=M;++i) Answer(keys[i]);
}