問題一覧 > 通常問題

No.1123 Afforestation

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 15
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007
3 ProblemId : 4633 / 出題時の順位表
問題文最終更新日: 2020-07-22 21:42:23

問題文

$H \times W$ のマス目がある。上から $i$ 番目、左から $j$ 番目のマスを $(i, j)$ とし、特に左上のマスを $(1, 1)$ とする。
$HW$ マスのうち $K$ マスには家が建設されており、その場所はマス $(x_1, y_1)$, $(x_2, y_2)$, ..., $(x_K, y_K)$ である。
さて、E869120 君は、以下の条件を満たすように、家のない各マスに木を $1$ 本植えるかどうか選びたい。

  • $i$ 行目 $(1 \leq i \leq H)$ に、合計で丁度 $A_i$ 本の木を植える。
  • $j$ 列目 $(1 \leq j \leq W)$ に、合計で丁度 $B_j$ 本の木を植える。
そのとき、条件を満たすような木の植え方が存在するか、求めなさい。
もし存在するならば、そのような植え方を 1 つ出力しなさい。

入力

$H$ $W$
$A_1$ $A_2$ $A_3$ ... $A_H$
$B_1$ $B_2$ $B_3$ ... $B_W$
$K$
$x_1$ $y_1$
$x_2$ $y_2$
$x_3$ $y_3$
: :
$x_K$ $y_K$

$1$ 行目に、整数 $H$, $W$ が空白区切りで与えられる。
$2$ 行目に、整数 $A_1$, $A_2$, ..., $A_H$ が空白区切りで与えられる。
$3$ 行目に、整数 $B_1$, $B_2$, ..., $B_W$ が空白区切りで与えられる。
$4$ 行目に、整数 $K$ が与えられる。
$5+i$ $(1 \leq i \leq K)$ 行目に、整数 $x_i, y_i$ が空白区切りで与えられる。

出力(木の植え方が存在しない場合)

$1$ 行に、:( と出力しなさい。

出力(木の植え方が存在する場合)

以下のように、$H+1$ 行に渡って出力しなさい。

  • $1$ 行目には、Yay! と出力する。
  • $1 \leq i \leq H$ について、$i+1$ 行目には $W$ 文字の文字列を出力する。文字列の $j$ ($1 \leq j \leq W$)文字目は、以下の通りでなければならない。
    • マス $(i, j)$ に家がある場合、x
    • マス $(i, j)$ に家がなく、そのマスに木を植える場合、o
    • マス $(i, j)$ に家がなく、そのマスに木を植えない場合、.

制約

  • $1 \leq H, W \leq 2 \ 000$
  • $0 \leq A_i \leq W$
  • $0 \leq B_i \leq H$
  • $1 \leq x_i \leq H$
  • $1 \leq y_i \leq W$
  • $0 \leq K \leq 16$
  • $(x_i, y_i) \neq (x_j, y_j)$ $(i \neq j)$
  • 入力はすべて整数

サンプル

サンプル1
入力
3 3
1 1 1
1 1 1
3
1 1
2 2
3 3
出力
Yay!
xo.
.xo
o.x

他にも、以下のような出力が正解となる。条件を満たす出力が複数あれば、どれを出力しても正解になることに注意すること。

Yay!
x.o
ox.
.ox
サンプル2
入力
4 5
3 2 3 2
1 3 2 2 3
3
1 2
2 3
4 4
出力
:(

条件を満たすような木の植え方は、1 通りたりとも存在しない。

サンプル3
入力
8 8
7 6 5 5 4 4 3 2
7 7 6 5 5 2 2 2
3
8 6
8 7
8 8
出力
Yay!
ooooo.oo
oooooo..
ooooo...
ooooo...
ooo....o
oo...oo.
..ooo...
oo...xxx

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。