← 返回题目列表

Codeforces · 1070/B

B. 贝尔科姆纳佐尔

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

Berkomnadzor — 联邦通信、信息技术和大众媒体监督局 — 是伯兰联邦执行机构,旨在保护伯兰普通居民免受现代互联网的威胁。

Berkomnadzor 维护着禁止的 IPv4 子网列表(黑名单)和允许的 IPv4 子网列表(白名单)。 Berland 的所有互联网服务提供商 (ISP) 必须配置网络设备以阻止对所有与黑名单匹配的 IPv4 地址的访问。此外,ISP 必须提供对所有与白名单匹配的 IPv4 地址的访问(即不阻止)。如果 IPv4 地址与这些列表中的任何一个都不匹配,则由 ISP 决定是否阻止它。当且仅当 IPv4 地址与黑名单(白名单)中的某个子网匹配时,它才匹配黑名单(白名单)。一个IPv4地址可以同时属于白名单和黑名单,这种情况会导致矛盾(参见输出描述中无解决方案的情况)。

IPv4 地址是一个 32 位无符号整数,格式为 $$$a.b.c.d$$$,其中每个值 $$$a,b,c,d$$$ 称为一个八位位组,是从 $$$0$$$ 到 $$$255$$$ 的整数,以十进制表示。例如,IPv4 地址 $$$192.168.0.1$$$ 可以使用以下表达式 $$$192 \cdot 2^{24} + 168 \cdot 2^{16} + 0 \cdot 2^8 + 1 \cdot 2^0$$$ 转换为 32 位数字。第一个八位字节 $$$a$$$ 编码最重要(最左边)$$$8$$$ 位,八位字节 $$$b$$$ 和 $$$c$$$ — 接下来的 $$$8$$$ 位块(按此顺序),八位字节 $$$d$$$ 编码最不重要(最右边)$$$8$$$ 位。

Berland 的 IPv4 网络与世界其他地区略有不同。 Berland 中没有保留地址或内部地址,并使用所有 $$$2^{32}$$$ 可能的值。

IPv4 子网表示为 $$$a.b.c.d$$$ 或 $$$a.b.c.d/x$$$(其中 $$$0 \le x \le 32$$$)。子网 $$$a.b.c.d$$$ 包含单个地址 $$$a.b.c.d$$$。子网 $$$a.b.c.d/x$$$ 包含 $$$x$$$ 最左边(最高有效)位等于地址 $$$a.b.c.d$$$ 最左边位的所有 IPv4 地址。要求子网 $$$a.b.c.d/x$$$ 的 $$$32 - x$$$ 最右边(最低有效)位为零。

自然地,所有与子网 $$$a.b.c.d/x$$$ 匹配的地址都会形成一个连续的范围。该范围从地址 $$$a.b.c.d$$$ 开始(最右边的 $$$32 - x$$$ 位为零)。该范围以 $$$x$$$ 最左位等于地址 $$$a.b.c.d$$$ 最左位的地址结束,并且其 $$$32 - x$$$ 最右位均为 1。子网恰好包含 $$$2^{32-x}$$$ 地址。子网 $$$a.b.c.d/32$$$ 仅包含一个地址,也可以仅用 $$$a.b.c.d$$$ 表示。

例如子网 $$$192.168.0.0/24$$$ 包含 256 个地址范围。 $$$192.168.0.0$$$ 是该范围的第一个地址,$$$192.168.0.255$$$ 是最后一个地址。

Berkomnadzor 的工程师制定了一项计划来提高 Berland 全球网络的性能。他们不想同时维护白名单和黑名单,而是只想构建一个包含最少数量子网的优化黑名单。这个想法是阻止所有与优化黑名单匹配的 IPv4 地址并允许所有其余地址。当然,旧黑名单中的 IPv4 地址必须保持阻止状态,并且旧白名单中的所有 IPv4 地址仍必须允许。那些既不匹配旧黑名单也不匹配旧白名单的IPv4地址可能会被阻止或允许,无论它们之前的可访问性如何。

请编写一个程序,以黑名单和白名单作为输入并生成优化的黑名单。优化的黑名单必须包含尽可能少的子网数量,并满足上述所有 IPv4 地址可访问性要求。

源列表中的 IPv4 子网可以任意交叉。如果某个 IPv4 地址同时匹配源白名单和黑名单,请输出单个数字 -1。

输入

输入的第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 输入中 IPv4 子网的总数。

以下 $$$n$$$ 行包含 IPv4 子网。每行以“-”或“+”号开头,分别指示该子网是否属于黑名单或白名单。后面是 $$$a.b.c.d$$$ 或 $$$a.b.c.d/x$$$ 格式 ($$$0 \le x \le 32$$$) 的 IPv4 子网(不带任何空格)。黑名单始终至少包含一个子网。

输入中给出的所有 IPv4 子网均有效。整数不以额外的前导零开头。提供的 IPv4 子网可以任意相交。

输出

如果存在同时匹配白名单和黑名单的 IPv4 地址,则输出 -1。否则输出 $$$t$$$ — 优化黑名单的长度,后跟 $$$t$$$ 子网,每个子网占一个新行。子网可以按任意顺序打印。所有与源黑名单匹配的地址都必须与优化黑名单匹配。所有匹配源白名单的地址不得匹配优化黑名单。您可以通过以下两种方式之一打印子网 $$$a.b.c.d/32$$$:作为 $$$a.b.c.d/32$$$ 或作为 $$$a.b.c.d$$$。

如果有多个解,则输出任意一个。

示例

输入 #1

1
-149.154.167.99

输出 #1

1
0.0.0.0/0

输入 #2

4
-149.154.167.99
+149.154.167.100/30
+149.154.167.128/25
-149.154.167.120/29

输出 #2

2
149.154.167.99
149.154.167.120/29

输入 #3

5
-127.0.0.4/31
+127.0.0.8
+127.0.0.0/30
-195.82.146.208/29
-127.0.0.6/31

输出 #3

2
195.0.0.0/8
127.0.0.4/30

输入#4

2
+127.0.0.1/32
-127.0.0.1

输出#4

-1