問題一覧 > 通常問題

No.2025 Select kk-th Submultiset

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : 👑 hahho / テスター : ymatsux None
1 ProblemId : 8243 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-26 20:18:47

問題文

以下の条件を満たす正整数列SSが与えられます。

  1. SSは11以上NN以下の正整数のみを含む
  2. SSの中に数字vvはちょうどcvc_v個ある
  3. SSの要素は昇順に並んでいる
すべてのiiに対し、SSの長さLLの（連続とは限らない）部分列の中で、辞書順でkik_i番目に小さいものを出力してください。
ただし、2つの部分列は、取り出す添字が異なっても、列として同じであれば区別しません。

出力形式が特殊なため、ご注意ください。

入力

N LN\ L
c1 c2 … cNc_1\ c_2\ \ldots\ c_N
QQ
k1k_1
k2k_2
⋮\vdots
kQk_Q

1≤N≤41 \leq N \leq 4
1≤L≤1000001 \leq L \leq 100000
1≤ci≤L1 \leq c_i \leq L
1≤Q≤1000001 \leq Q \leq 100000
1≤ki≤10181 \leq k_i \leq 10^{18}

出力

QQ行出力してください。
ii行目には、辞書順でkik_i番目に小さい部分列に含まれる1の個数、2の個数、...、Nの個数を空白区切りで出力してください。もし答えが存在しない場合は、-1を代わりに出力してください。

サンプル

サンプル1
入力
3 3
2 2 2
4
1
2
3
6
出力
2 1 0
2 0 1
1 2 0
0 2 1

[1, 1, 2, 2, 3, 3]の長さ3の部分列は全部で7通りあり、辞書順で昇順に並べると、 [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 3], [2, 3, 3]です。 よって答えは、[1, 1, 2], [1, 1, 3], [1, 2, 2], [2, 2, 3]となります。

サンプル2
入力
3 4
1 2 3
3
6
1000
2
出力
-1
-1
1 1 2

[1, 2, 2, 3, 3, 3]の長さ4の部分列は5通りしかないので、辞書順で6番目及び1000番目となるものは存在しません。

サンプル3
入力
4 10000
3000 4000 5000 6000
10
55942252857
4458141060
63666330001
24577122417
6230172594
13176764039
38390431668
10881380094
1652774037
27502349659
出力
-1
2747 3375 1192 2686
-1
1600 3777 2883 1740
2647 3324 2663 1366
2256 1479 567 5698
733 1694 1712 5861
2385 3293 1312 3010
2906 3156 1463 2475
1426 2742 2624 3208

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