问题陈述

Recruit Co. 有一个服务器机房,由网格表示 N 行和 N 列。
让 (i, j) 表示行中的单元格 i (0 \leq i \lt N) 从顶部和列 j (0 \leq j \lt N)从服务器机房的左侧。
每个单元最多可包含一台计算机。
有 K 计算机类型和 100 服务器机房中各种类型的计算机。
一开始, 100 \times K 计算机已放置在 100 \times K 细胞,剩余的 N^2 - 100 \times K 单元格为空。
X-san 可以 移动 首先是计算机,然后是 连接 它们带有直电缆。
移动 和 连接 定义如下:
-
移动 :选择一台计算机并将其移动到上、下、左或右的相邻单元格之一。您可以多次移动计算机。每个动作应满足以下所有要求:
- 您无法将一台计算机移至另一台计算机已位于的单元格。
- 您无法将计算机移出网格。
-
连接 :选择两台计算机并用直通电缆将它们相互连接。每个连接应满足以下所有要求:
- 您选择的两台计算机必须位于同一行或同一列,中间没有其他计算机。
- 电缆不与任何其他电缆相交。 (允许在一台计算机上连接多条电缆。)
- 您不能将同一对计算机连接两次。
- 您选择的两台计算机必须不同(一台计算机不能用一根电缆将计算机与其自身连接)。
集群 是通过连接计算机创建的。
计算机 C_i 和 C_j 被认为是“在同一个集群中”当且仅当计算机
可以从计算机访问 C_j 可以通过计算机访问 C_i 通过通过电缆连接的计算机的路径。
X桑想要创造美好 集群 并增加 服务器机房的处理性能 尽可能多。
同一类型的计算机数量越多 集群越好 服务器机房的处理性能.
另一方面,不同类型的计算机对越多, 集群,越低 服务器机房的处理性能.
的 服务器机房的处理性能 计算如下:
- 表示 100 \times K 服务器机房中的计算机为 C_0, C_1, \cdots, C_{100K-1}
-
的 服务器机房的处理性能 是每个整数对上的以下点的总和 (i, j) 满意 0 \leq i \lt j \lt 100 \times K:
- 1 点如果 C_i 和 C_j 属于同一 集群 且具有相同类型
- -1 点如果 C_i 和 C_j 属于同一 集群 且属于不同类型
- 0 点如果 C_i 和 C_j 不属于同一 集群
考虑到X桑的体力负担, 移动s 和数量 连接s 必须小于或等于
总共 100 \times K 。
您的挑战是找到一种方法来最大化 服务器机房的处理性能 根据我们上面设置的所有限制。
评分
在每个测试用例中,如果 服务器机房的处理性能 大于 0 分,这将是案件的得分;否则,测试用例将被评分 0 点。
提交的分数是每个测试用例的总分。 在临时测试中,如果您的提交产生非法输出或某些测试用例超出时间限制,则提交本身将被判定为 WA or TLE ,提交的分数将为零。 在系统测试中,如果您提交的测试用例产生非法输出或超出时间限制,则只有这些测试用例的分数为零。
测试用例数量
-
临时测试:50
- 在临时测试中, 随机选择满足输入约束的 N 和 K 。
-
系统测试:2000
- 对于系统测试,每个系统将有 20 个数据输入 N 和 K 对(共 100 对)。
- 我们将发布 种子.txt (sha256=
0a50dccf4689292f69a36be0ea1a99767de055434b854f2b0bc7f1fd40f9033e) 比赛结束后。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或确保有足够的执行时间。
输入
输入是从标准输入 (stdin) 给出的,格式如下:
\(\begin{array}{lll}
N ~ K & & \\
c_{ 0,0 } & \ldots & c_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
c_{ N-1,0 } & \ldots & c_{ N-1,N-1 }
\end{array}\)
第一行包含两个整数 N 和 K。以下每一项 N lines 被赋予一串长度 N.
-
N 和 K 是代表服务器机房大小和计算机类型数量的整数,满足以下条件之一
- K=2 和 15 \leq N \leq 39
- K=3 和 18 \leq N \leq 42
- K=4 和 21 \leq N \leq 45
- K=5 和 24 \leq N \leq 48
-
c_{ i,j } 是表示初始状态的整数 i从顶部开始的第一个单元格和 j服务器机房左侧第一个单元格。 0 \leq c_{i,j} \leq K .
- c_{i,j} = 0 表示牢房内没有放置电脑 (i, j)。总有 N^2 - 100 \times K 细胞没有计算机。
- if 1 \leq c_{ i,j } \leq K,表示计算机类型 c_{i,j} 被放置在单元格中 (i,j)。可以保证 100 每种类型的计算机都放置在网格中。
输出
请按以下格式输出到标准输出(stdout):
\(
X \\
a_0 ~ b_0 ~ c_0 ~ d_0 \\
\vdots \\
a_{X-1} ~ b_{X-1} ~ c_{X-1} ~ d_{X-1} \\
Y \\
e_0 ~ f_0 ~ g_0 ~ h_0 \\
\vdots \\
e_{Y-1} ~ f_{Y-1} ~ g_{Y-1} ~ h_{Y-1}
\)
第一行,输出一个整数 X 代表数量 移动待制作。
关于以下内容 X 行,输出代表有关信息的四个整数 移动按其制作顺序排列。
整数 a_i, b_i, c_i, d_i 上线 i 代表 移动 计算机位于 (a_i, b_i) to (c_i, d_i)
然后输出一个整数 Y 代表数量 连接待制作。
关于以下内容 Y 行,输出代表信息的四个整数 连接.
整数 e_i, f_i, g_i, h_i 上线 i 代表 连接 之间的计算机位于 (e_i, f_i) 和计算机位于 (g_i, h_i).
此外,必须满足以下所有约束,否则提交将被判定为 WA.
- 0 \leq X, ~ 0 \leq Y
- X + Y \leq 100 \times K
- 的 移动和 连接s 必须满足问题陈述中所写的条件
如果输出多个解,则仅输出 第一 一个用于评分。您可以使用 Web 可视化工具来比较解决方案。
输入生成
每个用例均由测试用例生成器生成。
测试用例生成器在页面底部的链接中提供。
测试用例生成器按以下步骤生成用例。有关详细信息,请参阅确切的实现(但是,您不需要通读它)。
- K 是由 \mathit{seed} \mod 4 + 2。通过调整种子值,具有特定的输入 可以生成 K 值。
- N 是从满足输入条件的那些中均匀随机生成的。
- c_{i,j} 是从满足输入条件的那些中均匀随机生成的。
工具
- 输入生成器和可视化工具(网络版):可以显示动画。
- 输入生成器和可视化工具(本地版本): 你需要一个编译环境 Rust 语言.
- 示例解决方案(C++、Python):他们实施以下内容:
- 随机制作几个 移动s
- 从每台计算机, 连接 到右侧和/或底部(如果可以到达相同类型的计算机)
- 计算分数并将其输出到stderr
在比赛结束之前不允许共享可视化结果。
示例输入 1 复制
5 2 10000 00000 00200 00000 00111请注意,此输入仅用于解释目的,不满足输入的约束。
示例输出 1 复制
2 0 0 0 1 0 1 0 2 4 0 2 2 2 2 2 4 2 4 2 4 3 4 3 4 4
- 将计算机移至 (0, 0) to (0, 2) 移动两次。
- 连接所有计算机。
-
的 服务器机房的处理性能 此时为2。
- 有一个 集群 由所有计算机组成,4 台类型 1 计算机和 1 台类型 2 计算机。
- 中的 1 类计算机对 集群 是 {4 \choose 2} = 6,并且有 4 \times 1 = 4 类型 1 和类型 2 之间的计算机对 集群,所以 服务器机房的处理性能 is 6 - 4 = 2 .
示例输入 2 复制
33 3 200000020020030300300012000000200 000000000333000000002200002030201 000100010000003200020000031001010 000023200000000000202300010000030 000010000023000300310300003000010 100010030001000032100000000103000 000000030100030300000000002000000 100000000120200000000000001001000 120030000200000000001001032000302 000000020003033020000013020002301 030000301300000000020200002003000 002000000020000000030103002000100 331210020020020000200200200103000 000202320000003000000000001000000 000010010030000303120001200000001 103000022010000313000000000000003 000012000010000001000000030000030 002000200003010100000002332000000 000003023000230020000003030000130 010000020001202302210002102030000 000003000000100002002000002002000 010003000200200000010030103000212 001000300000300000130020000003120 000000320300200100300000030002200 000000100003000000020100000300000 010000130110030200200100000110000 000231100000113000102000201003010 000000100030100230000000021000030 300103010000010100100300001022000 201021000001001000020000002000333 000002030300000000030000103100300 020000110320030200012100001030300 000100000010000000020001220030021此案例是通过运行带有种子=的测试用例生成器生成的
1。输出示例被省略。