CF1765A Access Levels

BerSoft 是 Berland 最大的 IT 公司，Monocarp 是其安全部门的负责人。这一次，他遇到了有史以来最困难的任务。 具体来说，BerSoft 有 $n$ 名开发者，编号从 $1$ 到 $n$。内部网络上有 $m$ 份文档，编号从 $1$ 到 $m$。有一张访问需求表 $a$，其中 $a_{i,j}$（第 $i$ 行第 $j$ 个元素）为 $1$ 表示第 $i$ 个开发者应当有权访问第 $j$ 个文档，为 $0$ 表示不应有权访问。 为了限制访问，Monocarp 将执行以下操作： - 选择访问组的数量 $k \ge 1$； - 为每份文档分配一个访问组（编号为 $1$ 到 $k$ 的整数）和所需的访问等级（$1$ 到 $10^9$ 的整数）； - 为每位开发者分配 $k$ 个整数值（每个值在 $1$ 到 $10^9$ 之间），表示其在每个访问组的访问等级。 如果某开发者 $i$ 在某文档 $j$ 所属访问组的访问等级大于等于该文档的所需访问等级，则该开发者可以访问该文档。 请问 Monocarp 至少需要多少个访问组，才能通过分配访问组和访问等级，使得所有访问需求表中的要求都被满足？

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 500$），分别表示开发者数量和文档数量。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串，表示访问需求表。第 $i$ 行第 $j$ 个字符为 $1$ 表示第 $i$ 个开发者应有权访问第 $j$ 个文档，为 $0$ 表示不应有权访问。

第一行输出一个整数 $k$，表示 Monocarp 至少需要选择的访问组数量。 第二行输出 $m$ 个整数，范围为 $1$ 到 $k$，表示每份文档所属的访问组。 第三行输出 $m$ 个整数，范围为 $1$ 到 $10^9$，表示每份文档的所需访问等级。 接下来的 $n$ 行，每行输出 $k$ 个整数，范围为 $1$ 到 $10^9$，表示每位开发者在每个访问组的访问等级。 如果有多组解，输出任意一组均可。

在第一个样例中，我们将两份文档分配到不同的访问组。两份文档在各自的访问组中都设为等级 $2$。这样，需要访问的开发者可以分配等级 $2$，不需要访问的开发者分配等级 $1$。 如果将两份文档分配到同一个访问组，则无法为开发者 $1$ 和 $3$ 分配合适的访问等级。开发者 $1$ 在该组中应比开发者 $3$ 的等级低，才能无法访问文档 $1$；同时，开发者 $3$ 在该组中又应比开发者 $1$ 的等级低，才能无法访问文档 $2$。由于两者不可能互相都比对方低，因此只用一个访问组是不可能的。 在第二个样例中，可以将所有文档分配到同一个访问组。 由 ChatGPT 4.1 翻译