Cod sursa(job #459625)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 30 mai 2010 14:14:11
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#define nmax 30010

int n, m, k, p, v[4*nmax], sol[nmax], d[nmax];

int query(int nod, int l, int r)
{
	if (1<=l && r<=m) return v[nod]; else
	{
		int c=(l+r)/2, s=0;
		if (1<=c) s=query(2*nod, l, c);
		if (c<m) s+=query(2*nod+1, c+1, r);
		return s;
	}
}

int search(int a, int b)
{
	int x;
	m=0;
	while (a<=b)
	{
		m=(a+b)/2;
		m--;
		if (!m) x=d[k]; else
			x=query(1, 1, n)+d[k];
		m++;
		if (x<m) b=m-1; else
		if (x>m) a=m+1; else break; 
	}
	while (sol[m]) m++;
	return m;
}

void update(int nod, int l, int r)
{
	if (l==r) v[nod]++; else
	{
		int c=(l+r)/2;
		if (p<=c) update(2*nod, l, c); else
			update(2*nod+1, c+1, r);
		v[nod]=v[2*nod]+v[2*nod+1];
	}
}

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++) scanf("%d",&d[i]);
	for (k=n; k>0; k--)
	{
		p=search(1,n);
		update(1,1,n);
		sol[p]=k;
	}
	for (i=1; i<=n; i++) printf("%d\n",sol[i]);
}