Test Contest 2026/03/21 20:00 ~ 2026/03/27 08:00 132:00:00.000

E Subset Sum Challenge

問題
制限時間: 2 sec メモリ制限: 1024 MB
Subset Sum Challenge
Statement

整数 \(N,M\) と長さ \(N\) の数列 \(A=(A_1,A_2,\dots,A_N)\) が与えられる。

全ての要素が \(1\) 以上 \(M\) 以下である長さ \(N\) の数列 \(B\) を出力せよ。

得点については、得点計算の欄を参照せよ。

Input

入力形式

  • \(1\) 行目に \(N,M\) がこの順に与えられる。
  • \(2\) 行目に \(N\) 個の整数 \(A_1,A_2,\dots,A_N\) が与えられる。

入力生成方法

サンプル以外の入力は以下の方法で生成される。

  • \(N\) は \(20\) 以上 \(100\) 以下の整数から一様ランダムに選択される。
  • \(M\) は \(2\) 以上 \(10\) 以下の整数から一様ランダムに選択される。
  • \(A_i\) は \(1\) 以上 \(10^7\) 以下の整数から一様ランダムに選択される。

Output

\(N\) 個の整数 \(B_1,B_2,\dots,B_N\) をこの順で \(1\) 行に出力せよ。

Scoring

得点計算は次の手順で行う。

  • 全ての要素が \(0\) の長さ \(M\) の数列 \(S=(S_1,S_2,\dots,S_M)\) を用意する。
  • \(i=1,2,\dots,N\) について以下を繰り返す。
    • \(S_{B_i}\) に \(A_i\) を加算する。
  • \(S\) の最小値を \(S_{\rm min}\) 、最大値を \(S_{\rm max}\) とする。
  • このとき、 \(\lfloor 10^5 \times (30 - \log_{2}(S_{\rm max}-S_{\rm min}+1)) \rfloor\) をそのケースの得点とする。
  • テストケースはサンプル以外に \(100\) 個存在し、サンプルを含めた \(101\) 個のテストケースの得点の合計が最終的な得点となる。

Example

Input 1
4 2
3 6 6 3
Output 1
2 1 2 1

サンプル