### Permutation problem - "Time exceeded error " in coding

Hi All, Here is another problem which i have tried to decoded and land up with the same problem of "Time exceeded" . as i am a beginer , i am not able to debug the same inspite of tried the same for one full day. Every time the same error appears . Please help me in understanding and correcting the error in my code.

Problem 2: Find the Permutation, (Tanmoy Chakraborty, Indraneel Mukherjee, CMI)

A permutation of the numbers 1, ..., N is a rearrangment of these numbers. For example

2 4 5 1 7 6 3 8
is a permutation of 1,2, ..., 8. Of course,

1 2 3 4 5 6 7 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 ith 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 4 5 1 7 6 3 8
the inversion sequence is

0 1 0 2 2 1 2 0
The 2nd element is 1 because 1 is strictly less than 2 and it appears to the right of 2 in this permutation. Similarly, the 5th 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 7 6 5 4 3 2 1
is

0 1 2 3 4 5 6 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 format

The first line consists of a single integer N. The following line contains N integers, describing an inversion sequence.

Output format

A single line with N integers describing a permutation of 1, 2, ..., N whose inversion sequence is the given input sequence.

Test Data:

You may assume that N ≤ 100000. You may further assume that in at least 50% of the inputs N ≤ 8000.

Example:

Here are sample inputs and outputs corresponding to the example discussed above.

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 1

CPU Timelimit: 3 seconds
Memory limit: 64M

[b]Solution :

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
int n;
int a[8000],b[8000];
cin>>n;
int i,j,count;
for(i=0;i<n;i++)
{cin>>a[i];
b[i]=0;
}
for(i=n-1;i>-1;i--)
{count=a[i];
for(j=n-1;j>-1;j++)
{if(i+1>b[j])
{if(count=0)
{b[j]=i+1;}
else
{count--;}
}
}
}
for(i=0;i<n;i++)
{cout<<b[i];}
}
Topic archived. No new replies allowed.