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

Grading style: ioi

[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.