theater

2 secs 1024 MB
Ang107's icon Ang107
Tweet
問題
提出
テストケース
解説
ジャッジコード

注意

入出力の量が多くなることがあるため、高速な入出力を行うことを推奨します。
例:

問題文

あなたは、とある劇場の観客の座席割り当てを決定する仕事を行っています。
劇場は HH 行 WW 列の座席からなり、今回の公演には NN 人の観客が訪れます。 観客 ii の身長は AiA_i です。

観客が「快適に観る」ことができるのは、次の条件を満たすとき、かつそのときに限ります：

  • 同じ列において、自分より前の行にいる任意の観客の身長が自分より低い。

あなたは、それぞれの観客をいずれかの座席に割り当てるとき、「快適に観る」ことのできる人数を最大化したいと考えています。 そのときの「快適に観る」ことのできる人数と、座席表の一例を出力してください。 ( NN 人の観客全員をいずれかの座席に割り当てる必要があります。)

座席表は次の形式で表されます：

  • 前から ii 行目、左から jj 列目の座席を Si,jS_{i,j} とする。
  • Si,j=−1S_{i,j} = -1 なら空席、Si,j=kS_{i,j} = k なら観客 kk をその座席に割り当てたことを表す。

答えが複数考えられる場合、どれを出力しても正解とみなされます。

制約

  • 1≤H≤2×1051 \leq H \leq 2 \times 10^5
  • 1≤W≤2×1051 \leq W \leq 2 \times 10^5
  • 1≤HW≤2×1051 \leq HW \leq 2 \times 10^5
  • 1≤N≤HW1 \leq N \leq HW
  • 1≤Ai≤109 (1≤i≤N)1 \leq A_i \leq 10^9 \, (1 \leq i \leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

HH WW
NN
A1A_1 A2A_2 …\dots ANA_N

出力

1 行目に「快適に観る」ことのできる人数を出力してください。 続く HH 行に座席表を以下の形式で出力してください。

S1,1S_{1,1} S1,2S_{1,2} …\dots S1,WS_{1,W}
S2,1S_{2,1} S2,2S_{2,2} …\dots S2,WS_{2,W}
.
.
.
SH,1S_{H,1} SH,2S_{H,2} …\dots SH,WS_{H,W}

入力例 1

2 2
3
1 5 2

出力例 1

3
1 3
2 -1

このように割り当てることで 33 人全員が「快適に観る」ことができます。

入力例 2

3 2
6
1 1 1 1 1 1

出力例 2

2
5 4
6 3
2 1

どのように割り当てても 33 人以上が「快適に観る」ことはできません。

入力例 3

3 1
1
1000000000

出力例 3

1
-1
-1
1

提出

Go (1.21)