P3936 Coloring

$\text{Snakes}$ is playing a game where he colors squares on a white paper with $n\times m$ grid cells. However, messy coloring is not fun, so he came up with a peculiar problem: In an $n\times m$ grid, use $c$ different colors to try to color all cells. Different colors are represented by integers in $1...c$. The coloring must satisfy the following conditions: + Each cell must be colored in exactly one color. + Color $i$ must color exactly $p_i$ cells. It is guaranteed that $\sum_{i=1}^c p_i = n\times m$. + Consider cells that are adjacent up, down, left, or right and have the same color to be in the same connected component, and define $q$ as the number of grid edges between different connected components. See the sample explanation. Now, $\text{Snakes}$ wants to know, given $n$, $m$, $c$ and $p_1...p_c$, whether you can construct a valid coloring that makes $q$ as small as possible.

The first line contains three numbers, $n,m,c$. The second line contains $c$ numbers, where the $i$-th number is $p_i$.

Output $n$ lines, each containing $m$ numbers, representing your constructed $n\times m$ coloring with $q$ as small as possible.

```plain | | 2 | 3 | 1 + +--- 2 | 3 3 | ``` For the sample, $q=4$, consisting of three vertical edges and one horizontal edge. #### Conventions This problem is Special Judge. For each test point, a threshold $w$ is set, and it is guaranteed that there exists a construction such that $q\leq w$. The score for your output will be computed as follows: $$\begin{matrix}q&score&q&score\\\\ q \leq w&10&1.75w < q \leq 2w&5\\\\ w < q \leq 1.1w&9&2w < q \leq 2.3w&4\\\\ 1.1w < q \leq 1.25w&8&2.3w < q \leq 2.6w&3\\\\ 1.25w < q \leq 1.5w&7&2.6w < q \leq 3w&2\\\\ 1.5w < q \leq 1.75w&6&3w < q \leq 3.5w&1\end{matrix}$$ If $q > 3.5w$, it will be judged as `Wrong Answer`. The score shown during the contest is the final score. #### Constraints For $10\%$ of the testdata, $1\leq n,m\leq 3$, $c\leq 3$. For $30\%$ of the testdata, $1\leq n,m\leq 8$, $c\leq 6$. For $50\%$ of the testdata, $1\leq n,m\leq 15$, $c\leq 25$. For $100\%$ of the testdata, $1\leq n,m\leq 20$, $c\leq 50$, $p_i\leq 20$. Translated by ChatGPT 5