問題一覧 > 通常問題

No.1328 alligachi-problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 38
作問者 : ir_1st_vilir_1st_vil / テスター : 沙耶花沙耶花
4 ProblemId : 5572 / 出題時の順位表
問題文最終更新日: 2021-01-08 23:50:49

問題文

$1$ から $N$ までの番号が付いた $N$ 個のボールがあり、番号 $i$ のボールは色 $C_i$ で塗られています(ボールの色は赤または青)。これらのボールを任意の順序で左右一列に並べ、以下の条件が満たされるようにしたいです。

  • 全ての整数 $i\ (1 \le i \le N)$ について、番号 $i$ のボールより左には色 $X_i$ のボールが(そのボール自身を含まずに) $Y_i$ 個存在する。

この条件が満たされるような並べ方が存在するか判定し、存在するならば一つ示してください。

入力

$N$
$C_1\ X_1\ Y_1$
$C_2\ X_2\ Y_2$
$\vdots$
$C_N\ X_N\ Y_N$

  • 入力される数値はすべて整数
  • $1 \le N \le 2 \times 10^5$
  • $C_i, X_i$ はRまたはBでありそれぞれ赤と青を表す
  • $0 \le Y_i < N$

出力

条件が満たされるような並べ方が存在する場合は一行目にYes、二行目に $A_i=$ (左から $i$ 番目に置くボールの番号) として構成される長さ $N$ の整数列 $A$ を空白区切りで出力し、最後に改行してください。条件が満たされるような並べ方が複数ある場合はどれを出力しても構いません。ただし $1 \le A_i \le N$ と $A_i \neq A_j\ (i \neq j)$ がそれぞれ満たされていなければいけません。

Yes
$A_1\ A_2\ \dots\ A_N$

存在しない場合はNoと一行に出力し、最後に改行してください。

No

(2020/12/25 7:34 追記)末尾に余計な空白があるとWAになります、注意してください。

サンプル

サンプル1
入力
5
B R 1
R R 1
B B 2
R R 0
B B 0
出力
Yes
4 5 1 2 3

解は複数存在する可能性があります。例えばこのケースの場合 $(5,4,1,2,3)$ なども正解となります。

サンプル2
入力
4
R R 0
R R 0
B R 1
B B 1
出力
No

解が存在しないこともあります。

サンプル3
入力
10
B B 0
R R 2
R B 3
R B 1
R B 3
R B 3
R R 1
B B 2
R R 0
B R 4
出力
Yes
9 7 2 1 4 10 8 3 5 6

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