No.918 LISGRID
タグ : / 解いたユーザー数 45
作問者 :
tempura_pp
Problem Statement
There is a grid with $H$ rows and $W$ columns.
Initially, nothing is written in any of the cells.
Consider writing numbers in all $HW$ cells so that the following conditions are satisfied.
- The numbers written are between $1$ and $HW$, inclusive, and are all distinct.
- Consider an integer sequence $S_1,S_2,\dots\ ,S_H$ of length $H$.
Define the $i$-th ($1 \le i \le H$) element $S_i$ as "the length of the longest increasing subsequence of the sequence obtained by reading the $W$ numbers written in the $i$-th row of the grid in order from left to right".
By appropriately rearranging the order of the elements of this sequence $S$, it is possible to make it equal to the sequence $A$. - Consider an integer sequence $T_1,T_2,\dots\ ,T_W$ of length $W$.
Define the $j$-th ($1 \le j \le W$) element $T_j$ as "the length of the longest increasing subsequence of the sequence obtained by reading the $H$ numbers written in the $j$-th column of the grid in order from top to bottom".
By appropriately rearranging the order of the elements of this sequence $T$, it is possible to make it equal to the sequence $B$.
An increasing subsequence means "a subsequence of an integer sequence in which, for any $2$ adjacent elements, the right one is always strictly greater".
A longest increasing subsequence means "an increasing subsequence whose length is the longest".
Construct one grid with numbers written in it so that all of these conditions are satisfied.
It can be proved that at least one grid satisfying the conditions exists.
Input
$H\ W$
$A_{1}\ A_{2}\ \dots\ A_{H}$
$B_{1}\ B_{2}\ \dots\ B_{W}$
All inputs are integers.
$1 \le H,W \le 400$
$1 \le A_i \le W (1 \le i \le H)$
$1 \le B_i \le H (1 \le i \le W)$
Output
$C_{1,1}\ C_{1,2}\ \dots\ C_{1,W}$
$C_{2,1}\ C_{2,2}\ \dots\ C_{2,W}$
$\vdots$
$C_{H,1}\ C_{H,2}\ \dots\ C_{H,W}$
Output a grid satisfying the conditions in the format above.
The elements of the grid you output must be between $1$ and $HW$, inclusive, and all distinct.
Print a newline at the end.
Sample
Sample 1
Input
2 2 2 1 2 2
Output
2 1 3 4
For this sample output, $S=\{ 1,2 \},T=\{ 2,2 \}$, as shown in the figure.
The conditions are satisfied because rearranging the order of the elements of $S$ makes it equal to $A$, and $T$ is already equal to $B$.
Sample 2
Input
3 2 2 2 2 3 2
Output
1 5 2 3 4 6
There may be multiple valid answers.
Sample 3
Input
2 5 2 3 2 1 2 1 2
Output
10 9 2 1 7 4 3 6 5 8
Note that the definition of a subsequence does not include "being contiguous in the original sequence".
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。