Kyoto University Programming Contest 2018

G - 数列を構成する問題


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 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 は、ji を割り切ることを意味します。

制約

  • 入力は全て整数である。
  • 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 = 0b_2 = a_1 + a_2 = 1b_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 つ目の条件を満たすことは不可能です。


Submit提出する