No.2025 Select $k$-th Submultiset
hahho
ymatsux
NoneProblem Statement
You are given a sequence $S$ of positive integers satisfying the following conditions.
- $S$ contains only positive integers between $1$ and $N$, inclusive.
- The number $v$ appears exactly $c_v$ times in $S$.
- The elements of $S$ are sorted in ascending order.
Here, two subsequences are not distinguished if they are identical as sequences, even if the indices they are taken from differ.
Note that the output format is unusual.
Input
$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}$
Output
Output $Q$ lines.
On the $i$-th line, output the number of 1s, the number of 2s, ..., and the number of Ns contained in the $k_i$-th lexicographically smallest subsequence, separated by spaces. If no such subsequence exists, output -1 instead.
Sample
Sample 1
Input
3 3 2 2 2 4 1 2 3 6
Output
2 1 0 2 0 1 1 2 0 0 2 1
[1, 1, 2, 2, 3, 3] has 7 subsequences of length 3 in total. Sorted in ascending lexicographic order, they are [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 3], [2, 3, 3]. Therefore, the answers are [1, 1, 2], [1, 1, 3], [1, 2, 2], [2, 2, 3].
Sample 2
Input
3 4 1 2 3 3 6 1000 2
Output
-1 -1 1 1 2
[1, 2, 2, 3, 3, 3] has only 5 subsequences of length 4, so the 6th and 1000th lexicographically smallest ones do not exist.
Sample 3
Input
4 10000 3000 4000 5000 6000 10 55942252857 4458141060 63666330001 24577122417 6230172594 13176764039 38390431668 10881380094 1652774037 27502349659
Output
-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もしくは右上の雲マークをクリックしてアカウントを作成してください。