← 返回题目列表

Codeforces · 1765/A

A. 访问级别

中文机器翻译题面 查看原题

BerSoft 是 Berland 最大的 IT 公司,Monocarp 是其安全部门的负责人。这一次,他面临着有史以来最艰巨的任务。

基本上,有 $$$n$$$ 开发人员在 BerSoft 工作,编号从 $$$1$$$ 到 $$$n$$$。内网共享了$$$m$$$个文档,编号从$$$1$$$到$$$m$$$。有一个访问要求表$$$a$$$,如果第$$$i$$$个开发人员应该有权访问第$$$j$$$个文档,则$$$a_{i,j}$$$(第$$$i$$$行的第$$$j$$$个元素)为$$$1$$$,如果他们无权访问该文档,则为$$$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$$$ 个文档,则第 $$$i$$$ 行的第 $$$j$$$ 个元素为 $$$1$$$;如果他们无权访问该文档,则第 $$$j$$$ 个元素为 $$$0$$$。

输出

第一行应包含一个整数 $$$k$$$ — Monocarp 可以选择的最小访问组数,以便可以分配访问组和访问级别以满足访问要求表。

第二行应包含从 $$$1$$$ 到 $$$k$$$ 的 $$$m$$$ 整数 - 文档的访问组。

第三行应包含从 $$$1$$$ 到 $$$10^9$$$ 的 $$$m$$$ 整数 - 文档所需的访问级别。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行应包含从 $$$1$$$ 到 $$$10^9$$$ 的 $$$k$$$ 整数 - 每个访问组中第 $$$i$$$ 开发人员的访问级别。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 2
01
11
10

输出 #1

2
1 2 
2 2 
1 2 
2 2 
2 1

输入 #2

2 3
101
100

输出 #2

1
1 1 1
1 10 5
8
3

注意

在第一个示例中,我们将文档分配给不同的访问组。两个文档的访问组中的级别均为 $$$2$$$。这样,我们可以为需要访问权限的开发人员分配级别 $$$2$$$,为不需要访问权限的开发人员分配级别 $$$1$$$。

如果他们具有相同的访问组,则无法为开发人员 $$$1$$$ 和 $$$3$$$ 分配访问级别。该组中开发人员 $$$1$$$ 的级别应该低于开发人员 $$$3$$$,因此无法访问文档 $$$1$$$。同时,该组中开发人员$$$3$$$ 的级别应低于开发人员$$$1$$$,因此无法访问文档$$$2$$$。由于它们的级别不能都低于对方,因此不可能只有一个访问组。

在第二个示例中,可以将所有文档分配到同一访问组。