問題一覧 > 通常問題

No.918 LISGRID

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 45
作問者 : ningenMe / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 3092 / 自分の提出
問題文最終更新日: 2020-12-06 13:00:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 229 (順位表) の他の問題:

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$.
  •   
Here, a subsequence means "an integer sequence obtained by choosing and deleting some $0$ or more elements of an integer sequence and arranging the remaining elements in their original order".
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もしくは右上の雲マークをクリックしてアカウントを作成してください。