Cannot parse: undefinedms error parsing time

题目描述

译自 JOI Open 2013 T1 「一票の格差 / Vote-Value Disparity」

由 $N$ 个省份组成的 JOI 王国将要举行一场全国性的选举。

JOI 王国是一个由 $H \times W$ 个方块组成的矩形网格。在垂直方向上有 $H$ 个方块，在水平方向上有 $W$ 个方块。每个方块都与上下左右相邻的方块相连。$H \times W$ 个方块被划分为 $N$ 个省份。每个省份是由若干个方块组成的一个连通块。第 $i\ (1 \leq i \leq N)$ 个省份有 $P_{i}$ 个选民。

你是 JOI 国家选举委员会的主席。你的任务是将 $N$ 个省份划分为 $K\ (1 \leq K \leq N)$ 个选区，每个选区会有一个代表。每个选区应该包含至少一个省份，而且属于同一个选区的方块应该形成一个连通块。注意方块只与上下左右相邻的方块联通，跟对角相邻的方块不联通。

对于每个选区，令 $c$ 为选区中的选民数，该选区的单票权重为 $\frac{1}{c}$。一票的差距被定义为所有选区的单票权重的最大值除以所有选区的单票权重的最小值。

给定 JOI 王国的省份信息和代表的数量，你需要给出将省份划分为选区的方案，使得一票的差距的值尽可能小。

输入格式

第一行包含四个用空格分隔的整数 $H, W, N, K$，表示 JOI 王国的地图的高度是 $H$，宽度是 $W$，省份的数量是 $N$，代表的数量是 $K$。

接下来的 $H$ 行中的每一行包含 $W$ 个用空格分隔的整数。在第 $i\ (1 \leq i \leq H)$ 行中，第 $j\ (1 \leq j \leq W)$ 个整数是 $S_{i,j}$，表示从上到下的第 $i$ 行，从左到右的第 $j$ 列的方块属于第 $S_{i,j}$ 个省份。

在接下来的 $N$ 行中的第 $i\ (1 \leq i \leq N)$ 行包含一个整数 $P_{i}$，表示第 $i$ 个省份的选民数。

输出格式

输出 $N$ 行，第 $i\ (1 \leq i \leq N)$ 行包含一个整数，表示第 $i$ 个省份所属的选区的编号。

2 3 4 3
1 1 1
2 3 4
3
5
7
10

1
2
1
3

在这个样例中，JOI 王国的形状如下。

每个省份的选民数分别是 $3,5,7,10$。在这个样例输出中，省份被划分为以下选区。

• 选区 $1$：省份 $1$ 和省份 $3$
• 选区 $2$：省份 $2$
• 选区 $3$：省份 $4$

每个选区的选民数分别是 $10,5,10$。每个选区的单票权重分别是 $0.1,0.2,0.1$。因此，选票价值差异是 $0.2 / 0.1=2$。如果 $X=1.5, Y=3$，我们有 $\left(\frac{3-2}{3-1.5}\right)^{2} \times 20=8.8 \cdots$，这个输出值 $8$ 分。

以下划分是不合法的，因为选区 $2$ 不形成一个连通块。

• 选区 $1$：省份 $1$
• 选区 $2$：省份 $2$ 和省份 $4$
• 选区 $3$：省份 $3$

计分

对于每个输入，你的分数按以下方式计算。

如果你的输出不满足任务陈述中的条件，你的分数是 $0$。如果满足条件，设 $D$ 表示你的输出的一票的价值。然后你的分数按以下方式计算。

• 如果 $Y<D$，你的分数是 $0$。
• 如果 $X<D \leq Y$，你的分数是 $\left(\frac{Y-D}{Y-X}\right)^{2} \times 20$ 保留整数部分的值。
• 如果 $D \leq X$，你的分数是 $20$。

对于每个测试点，$X,Y$ 的值如下表所示。

测试点编号	$X$	$Y$
$1$	$1.02$	$2$
$2$	$1.66$	$2.5$
$3$	$1.06$	$2.5$
$4$	$1.005$	$3$
$5$	$1.0005$	$2$

数据范围与提示

对于所有输入数据，满足：

• $1 \leq H \leq 200$
• $1 \leq W \leq 200$
• $1 \leq N \leq 10000$
• $1 \leq K \leq N$
• $1 \leq P_{i} \leq 10^5\ (1 \leq i \leq N)$
• $1 \leq S_{i,j} \leq N\ (1 \leq i \leq H,1 \leq j \leq W)$
• 对于每个省份，属于该省份的方块形成一个连通块。