Cod sursa(job #64448)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 3 iunie 2007 12:39:08
Problema Schi Scor 100
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];

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,tmp,lo,hi;
	lo=1; hi=N;
	while ( lo <= hi ) {
		m = ( lo + hi ) / 2;
		tmp=m-query(m);
		if ( tmp == val ) {
			--m;
			if ( m - query(m) == val )
				hi=m;
			else
				return m+1;
		}
		else
		if ( tmp < val )
			lo=m+1;
		else
			hi=m-1;
	}
	return -1;
}

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;
}