問題一覧 > 通常問題

No.2042 RGB Caps

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 110
作問者 : koboshikoboshi / テスター : 👑 KazunKazun 👑 hitonanodehitonanode
20 ProblemId : 7149 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-20 00:23:01

問題文

$N$ 人の生徒が一列に並んでおり、赤、緑、青のいずれかの帽子をかぶっています。列の先頭から $1,2,\ldots,N$ と生徒に番号を付けることにします。

$K$ 個の証言を得ました。$i$ 番目の証言は次のようなものでした。

  • $1$ 番目から $A_i$ 番目までの生徒の帽子の中で最も多く現れる色の一つは $c_i$ である。

ただし $c_i$ は R, G, B のいずれかで、それぞれ赤、緑、青を表します。また $i\ne j$ ならば $A_i\ne A_j$ をみたします。

これらの証言をもとに生徒たちの帽子の被り方としてあり得るものを $1$ つ求めてください。ただし証言が矛盾している場合はその旨を報告してください。

制約

  • $1\le K\le N\le 10^5$
  • $1\le A_i\le N$
  • $i\ne j$ ならば $A_i\ne A_j$
  • $c_i$ は R, G, B のいずれか
  • $N,K,A_i$ は整数

入力

$N$ $K$
$A_1$ $c_1$
$\vdots$
$A_K$ $c_K$

出力

証言が矛盾している場合は $-1$ を出力してください。

そうでないとき、$1$ 行に $N$ 文字出力してください。$i$ 文字目は、$i$ 番目の生徒が赤の帽子を被っているとき R、緑の帽子を被っているとき G、青の帽子を被っているとき B としてください。

答えが複数ある場合、どれを出力しても構いません。

サンプル

サンプル1
入力
5 3
3 G
5 B
1 R
出力
RGGBB
  • $1$ つ目の証言について:$1$ 番目から $3$ 番目の生徒の中に赤の帽子が $1$ 人、緑の帽子が $2$ 人いるので、最も多く現れる色は緑です。
  • $2$ つ目の証言について:$1$ 番目から $5$ 番目の生徒の中に赤の帽子が $1$ 人、緑の帽子が $2$ 人、青の帽子が $2$ 人いるので、最も多く現れる色は緑と青です。
  • $3$ つ目の証言について:$1$ 番目の生徒は赤の帽子なので、最も多く現れる色は赤です。

よってこの出力は条件を満たします。

サンプル2
入力
12 5
2 R
3 R
5 R
7 R
11 B
出力
RRRBRBRBBBBB

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