Cod sursa(job #64450)

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

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

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

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

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

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(v[i]);
		ret[p]=i;
		ins(p,1);		
	}
	
	for ( i=1;i<=N;++i )
		printf("%d\n",ret[i]);
	
	return 0;
}