No.2025 Select $k$-th Submultiset
タグ : / 解いたユーザー数 29
作問者 :
hahho28
/ テスター :
ymatsux
None
問題文
以下の条件を満たす正整数列$S$が与えられます。
- $S$は$1$以上$N$以下の正整数のみを含む
- $S$の中に数字$v$はちょうど$c_v$個ある
- $S$の要素は昇順に並んでいる
ただし、2つの部分列は、取り出す添字が異なっても、列として同じであれば区別しません。
出力形式が特殊なため、ご注意ください。
入力
$N\ L$ $c_1\ c_2\ \ldots\ c_N$ $Q$ $k_1$ $k_2$ $\vdots$ $k_Q$
$1 \leq N \leq 4$
$1 \leq L \leq 100000$
$1 \leq c_i \leq L$
$1 \leq Q \leq 100000$
$1 \leq k_i \leq 10^{18}$
出力
$Q$行出力してください。
$i$行目には、辞書順で$k_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もしくは右上の雲マークをクリックしてアカウントを作成してください。