CF1621E New School

你决定开办一所新学校。你已经找到了 $n$ 位老师和 $m$ 个学生小组。第 $i$ 个学生小组由 $k_i \geq 2$ 名学生组成。你知道每位老师和每位学生的年龄。老师们的年龄为 $a_1, a_2, \ldots, a_n$，第 $i$ 个小组学生的年龄为 $b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$。 要开始上课，你需要为每个学生小组分配一位老师。这样的分配需要满足以下要求： - 每个小组恰好分配一位老师。 - 每位老师最多只能分配给 $1$ 个学生小组。 - 每个小组学生的平均年龄不超过分配给该组的老师的年龄。 一组 $x_1, x_2, \ldots, x_k$ 的平均值为 $\frac{x_1 + x_2 + \ldots + x_k}{k}$。 最近你听说有一名学生将拒绝在你的学校学习。这样，某个小组的人数将减少 $1$，其他小组不变。 你不知道具体是哪位学生会拒绝。对于每一名学生，请判断如果他拒绝学习，是否仍然可以开始上课。 注意，最初并不保证一定可以开始上课。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 10^5$），分别表示老师的数量和学生小组的数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^5$），表示每位老师的年龄。 接下来的 $2m$ 行描述各个小组。 每个小组的描述的第一行包含一个整数 $k_i$（$2 \leq k_i \leq 10^5$），表示该小组的学生人数。 每个小组的描述的第二行包含 $k_i$ 个整数 $b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$（$1 \leq b_{i, j} \leq 10^5$），表示该小组每位学生的年龄。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，所有测试用例中 $k_1 + k_2 + \ldots + k_m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个由 $0$ 和 $1$ 组成的字符串，长度为 $k_1 + k_2 + \ldots + k_m$。如果第 $i$ 位学生拒绝学习后仍然可以开始上课，则该位置输出 $1$，否则输出 $0$。 学生按输入顺序编号。即，第 $1$ 个小组的学生编号为 $1, 2, \ldots, k_1$，第 $2$ 个小组的学生编号为 $k_1+1, k_1+2, \ldots, k_1+k_2$，以此类推。

在第一个测试用例中，有一个学生小组，平均年龄为 $\frac{25+16+37}{3}=26$，有一位老师年龄为 $30$。只有一种分配方式可以开始上课。 如果年龄为 $16$ 的学生拒绝学习，该组学生的平均年龄变为 $\frac{25+37}{2}=31$，此时没有任何分配方式可以开始上课。 在第二个测试用例中，最初无法开始上课。然而，如果第 $3$ 位年龄为 $111$ 的学生拒绝学习，则各组的平均年龄分别变为 $\frac{4+5}{2}=4.5$ 和 $\frac{11+11}{2}=11$。此时可以将第一个小组分配给第一位老师，将第二个小组分配给第三位老师。 由 ChatGPT 4.1 翻译