
Find the Permutation
|
All submissions for this problem are available.
A permutation of the numbers $1, ..., N$ is a rearrangment of these numbers. For example $$2 \quad 4 \quad 5 \quad 1 \quad 7 \quad 6 \quad 3 \quad 8$$ is a permutation of $1,2, ..., 8$. Of course, $$1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8$$ is also a permutation of $1, 2, ..., 8$. Associated with each permutation of $N$ is a special sequence of positive integers of length $N$ called its inversion sequence. The $i^{th}$ element of this sequence is the number of numbers $j$ that are strictly less than $i$ and appear to the right of $i$ in this permutation. For the permutation $$2 \quad 4 \quad 5 \quad 1 \quad 7 \quad 6 \quad 3 \quad 8$$ the inversion sequence is $$0 \quad 1 \quad 0 \quad 2 \quad 2 \quad 1 \quad 2 \quad 0$$ The $2^{nd}$ element is $1$ because $1$ is strictly less than $2$ and it appears to the right of $2$ in this permutation. Similarly, the $5^{th}$ element is $2$ since $1$ and $3$ are strictly less than $5$ but appear to the right of $5$ in this permutation and so on. As another example, the inversion sequence of the permutation $$8 \quad 7 \quad 6 \quad 5 \quad 4 \quad 3 \quad 2 \quad 1$$ is $$0 \quad 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7$$ In this problem, you will be given the inversion sequence of some permutation. Your task is to reconstruct the permutation from this sequence. ###Input: The first line consists of a single integer $N$. The following line contains $N$ integers, describing an inversion sequence. ###Output: A single line with N integers describing a permutation of $1, 2, ..., N$ whose inversion sequence is the given input sequence. ###Constraints: - $1 \leq N \leq 100000$. - You may further assume that in at least $50 \%$ of the inputs $1 \leq N \leq 8000$. ###Sample Input 1 8 0 1 0 2 2 1 2 0 ###Sample Output 1 2 4 5 1 7 6 3 8 ###Sample Input 2 8 0 1 2 3 4 5 6 7 ###Sample Output 2 8 7 6 5 4 3 2 1Author: | admin2 |
Date Added: | 17-09-2018 |
Time Limit: | 2 sec |
Source Limit: | 50000 Bytes |
Languages: | C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS |
Comments
- Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
