Cod sursa(job #64439)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 3 iunie 2007 12:28:41
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>
#define fin  "schi.in"
#define fout "schi.out"
#define Nmax 30001

int N,sum[Nmax],ret[Nmax];
int v[Nmax];

void ins(int x,int val) {
	for (; x<=N ; x += x & ~ (x-1) )
		sum[x]+=val;
}

int query(int x) {
int s=0;
	for ( ; x>0 ; x -= x & ~ (x-1) )
		s+=sum[x];
	return s;
}

int search(int lo,int hi,int val) {
int m;
	m = ( lo + hi ) / 2;
	if ( m - query(m) == val ) {
		--m;
		if ( m - query(m) == val )
			return search(lo,m,val);
		else
			return m+1;
	}
	else
	if ( m - query(m) < val )
		return search(m+1,hi,val);
	else
		return search(lo,m-1,val);
}

int main() {
int i,p;	
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d",&N);

	for (i=1;i<=N;++i)
		scanf("%d",&v[i]);	
	
	for (i=N;i>0;--i) {
		p=search(1,N,v[i]);
		ret[p]=i;
		ins(p,1);		
	}
	
	for ( i=1;i<=N;++i )
		printf("%d ",ret[i]);
	
	printf("\n");
	
	return 0;
}