Cod sursa(job #179860)

Utilizator DorinOltean Dorin Dorin Data 16 aprilie 2008 13:38:54
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
# include <stdio.h>

using namespace std;

# define input "schi.in"
# define output "schi.out"

# define max 30001

int a[max],d[max],pos[max];
int i,j,n,x;

# define bit(x) ((x&(x-1))^x)

void update(int val,int x)
{
	while(x <= n)
		a[x]+=val,
		x+= bit(x);
}
int search(int x)
{
    int sum, p, putere;
    for(putere=1;putere<n;putere <<= 1);
    for(sum = 0,p = 0; putere; putere >>= 1)
			if(p+putere <= n && sum+a[p+putere] < x) p+=putere,sum+=a[p];
            
    return p;
}

int main()
{
    freopen(input,"r",stdin);
    freopen(output,"w", stdout);
    
    scanf("%d\n",&n);    
    for(i = 1; i<= n; i++)   scanf("%d\n",&d[i]);        
	for(i = 1;i <= n; i++)   update(1,i);
    
    for(i=n;i;i--)
    {
		x = search(d[i]) + 1;
		pos[x] = i;
		update(-1,x);
    }
    
    for(i = 1; i <= n; i++) printf("%d\n",pos[i]);
    
    return 0;
}