Cod sursa(job #36093)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 22 martie 2007 22:37:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
# include <stdio.h>

# define  _fin  "schi.in"
# define  _fout "schi.out"

# define  maxn  30003


int arb[maxn], n, a[maxn], ord[maxn];

void update(int i, int add)
{
	int ii;
	for (ii=i; ii<=n; ii += ii & (-ii))
		arb[ii]+=add;
}

int  query(int i)
{
	int ii, ret=0;
	for (ii=i; ii>0; ii &= ii-1) ret += arb[ ii ];
	return ret;
}

int bsearch(int x)
{
	int i, step;
	for (step=1; step<=n; step<<=1); step>>=1;
	for (i=n; step; step>>=1)
		if ( i-step>=1 )
			if ( query(i-step) >= x ) i-=step;
	
	return i;
}

int main()
{
	freopen(_fin, "r", stdin);
	freopen(_fout,"w", stdout);
	int i, x;
	
	for (scanf("%d", &n), i=1; i<=n; i++) scanf("%d", a+i), update(i, 1);

	for (i=n; i>=1; i--) {
		x = bsearch(a[i]);
		ord[x]=i;
		update(x, -1);
	}
	
	for (i=1; i<=n; i++) printf("%d\n", ord[i]);
	
	return 0;
}