Permutation

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Given $K$ and digits $S_1,\ldots,S_K$ with $0\le S_i\le K-i$, define the zero-based lexicographic permutation index

$$N=\sum_{i=1}^{K}S_i(K-i)!.$$ Find the $N$-th permutation of $1,2,\ldots,K$. ## Input The first line contains $K$. The second line contains $S_1,\ldots,S_K$. ## Output Print the requested permutation. ## Subtasks - Subtask 1 — 20%: $K\le100$. - Subtask 2 — 30%: $K\le5000$. - Subtask 3 — 50%: $K\le50000$, $0\le S_i\le K-i$. ## Example ### Input ```text 4 2 1 1 0 ``` ### Output ```text 3 2 4 1 ``` ### Explanation The factoradic digits successively select the 3rd, 2nd, 2nd, and remaining elements.$$