A vault dial is set by choosing an arrangement of n integer notches. List all distinct arrangements of the given multiset of notch values in lexicographic order, numbered starting from 0. Given an index r, output the arrangement at position r in that list. It is guaranteed that r is a valid index (0 ≤ r < number of distinct arrangements).
Line 1: two integers n and r.
Line 2: n space-separated integers, the multiset of notch values.
n space-separated integers on one line: the r-th arrangement in lexicographic order.
Example 1
Input
3 2 1 2 3
Expected
2 1 3
Explanation
Arrangements in order: 123,132,213,231,312,321. Index 2 is 2 1 3.
Example 2
Input
3 0 3 1 2
Expected
1 2 3
Explanation
Index 0 is always the smallest arrangement of the multiset {1,2,3}, which is 1 2 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →