外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

H - Too Heavy Sequence

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 350 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんは、NN 個の正整数からなる数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) を持っていますが、数が多すぎて重いので、長さを MM に減らしたいと考えています。

わりとねこくんは、数列に対して以下の操作を行えなくなるまで繰り返します。

  • 隣接する 22 つの要素、つまりAi=Ai+1=kA_i = A_{i+1} = kとなるようなi,i+1(1≤i≤N−1)i, i+1 (1 \le i \le N-1)を選び、数列AAからi,i+1i, i+1番目の要素を削除する。

    • k≥2k \ge 2 である場合、その 22 つの要素を数列から削除し、元の位置に k−1k - 1 を 11 つ挿入する(これにより、数列の長さはちょうど 11 減少する)。
    • k≤1k \le 1 である場合、操作は行わず、次の操作に移る。

    なお、条件を満たす隣接ペアが複数存在する場合、最も左にあるペアを優先して選んで操作を行います。

操作を行えなくなった時点で、数列の長さがちょうど MM となるような初期の数列 aa を 11 つ構築してください。
なお、条件を満たす数列 AA が複数存在する場合、どれを出力しても構いません。 ここで、条件を満たす数列 AA が必ず 11 つ以上存在することが保証されます。

制約

  • 1≤M≤N≤2×1051 \le M \le N \le 2 \times 10^5
  • 入力はすべて整数
  • 条件を満たすような AA が 11 つ以上存在する

出力する数列の制約

  • AiA_i は正の整数(1≤Ai≤1091 \le A_i \le 10^9)でなければならない。

入力

入力は以下の形式で標準入力から与えられます。

NMN \quad M

出力

条件を満たす数列 a=(a1,a2,…,aN)a = (a_1, a_2, \dots, a_N) の各要素を、空白区切りで 11 行に出力してください。

A1A_1 A2A_2 …\dots ANA_N

サンプル 1

入力

4 1

出力

3 3 3 3

A=(3,3,3,3)A = (3, 3, 3, 3) とすると、操作は以下のように進みます。

  1. 最も左にある等しいペア(1,21, 2 番目)の (3,3)(3, 3) が選ばれ、22 に置き換わります。数列は (2,3,3)(2, 3, 3) になります。
  2. 等しいペア(2,32, 3 番目)の (3,3)(3, 3) が選ばれ、22 に置き換わります。数列は (2,2)(2, 2) になります。
  3. 等しいペア(1,21, 2 番目)の (2,2)(2, 2) が選ばれ、11 に置き換わります。数列は (1)(1) になります。

これ以上操作を行えず、最終的な数列の長さは 11 となり、M=1M = 1 を満たすため正解となります。

サンプル 2

入力

6 2

出力

3 4 4 2 3 3

スペシャルジャッジ問題です。

参加受付は終了しました。