PERMTGEN - Permutation Generator
Hasan Jaddouh has invented a new algorithm for generating permutations this algorithm takes an array with length N as input and generate a permutation with length N from this array.
The array must satisfy (1 <= Ai <= i) in order for the resulting array to be a permutation. Here is the pseudo code of the algorithm:
read N for i=1 to N do read A[i] for i=1 to N do for j=1 to i-1 do if A[j] >= A[i] do A[j] = A[j]+1 for i=1 to N do print A[i]
but unfortunately for Hasan Jaddouh, his algorithm is too slow for big arrays so he asked you to help him to find a fast way to implement his algorithm.
your program should read input same as the pseudo code and output the new array.
Input
first line contains integer N (1 <= N <= 105).
second line contains N integers separated by spaces each integer is between 1 and 109 inclusive.
Note: in order for Hasan Jaddouh's algorithm to work and generate a permutation the constraint (1 <= Ai <= i) must be satisfied but to make this problem harder this constraint is not guaranteed so it's also not necessary that the output is a permutation.
Output
Output N integers separated by spaces, the new array after applying Hasan Jaddouh's algorithm.
Example
Input: 4 4 2 1 3 Output: 7 4 1 3
hide comments
Oleg:
2023-07-29 20:09:13
Solution from https://www.spoj.com/problems/KHAOTMPL accepted without any changes. Last edit: 2023-07-29 20:10:33 |
|
Pushkar Mishra:
2013-05-13 03:09:15
Finally got the bug. My algorithm becomes n^2 for the worst case when all elements of the actual array are 1.
|
|
Pushkar Mishra:
2013-05-12 17:44:33
I am pretty sure my algorithm is nlogn for all inputs. How can I make output faster?
|
|
Pushkar Mishra:
2013-05-12 15:19:30
@Author: It is a great question. I have almost got it correct. Can you please provide some tricky test cases. It will be of great help. you can email me as well: pushkar72@hotmail.com
|
|
Pushkar Mishra:
2013-05-12 08:27:09
My program gives SIGSEGV error. My code runs fine on my machine and on several online compilers. Please check. Submission ID: 9246288
|
|
Pushkar Mishra:
2013-05-11 14:34:07
Time limit is too strict for python and java.
|
Added by: | Hasan Jaddouh |
Date: | 2013-05-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |