G - 数列を構成する問題
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
次を満たす N 要素の整数列 a_1, a_2, ..., a_N を構成してください。
- 0 \leq a_i \leq 10^{12}
- M 個の整数 c_1, c_2, ..., c_M について、a_{c_i} = 0
- b_i = Σ _{j | i} a_j としたとき、1 \leq i \leq N-1 を満たす各 i について、b_i < b_{i+1}
ここで j | i は、j が i を割り切ることを意味します。
制約
- 入力は全て整数である。
- 1 \leq N \leq 3 \times 10^5
- 1 \leq M \leq N
- 1 \leq c_i \leq N
- M 個の整数 c_1, c_2, ..., c_M は全て異なる。
入力
入力は以下の形式で標準入力から与えられる。
N M c_1 c_2 ... c_M
出力
問題文の条件を満たす数列を構成できない場合は No
を出力せよ。
構成できる場合は Yes
を出力したあとに、条件を満たす数列の各要素を順に出力せよ。
入力例1
3 1 1
出力例1
Yes 0 1 2
この数列の各要素は非負整数なので、問題文の 1 つ目の条件を満たしています。
また a_1 = 0 なので、2 つ目の条件を満たしています。
さらに b_1 = a_1 = 0、b_2 = a_1 + a_2 = 1、b_3 = a_1 + a_3 = 2 であり、3 つ目の条件も満たしています。
入力例2
3 3 1 2 3
出力例2
No
この場合、a_1 = a_2 = a_3 = 0 である必要がありますが、このとき必ず b_1 = b_2 = b_3 = 0 となるため、3 つ目の条件を満たすことは不可能です。