Cod sursa(job #459632)

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

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

int query(int poz)
{
	int r=0;
	for (; poz; poz &= poz-1) r+=v[poz];
	return r;
}

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

void update(int poz)
{
	for (; poz<=n; poz += (poz & (poz-1))^poz)
		v[poz]++;
}

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(p);
		sol[p]=k;
	}
	for (i=1; i<=n; i++) printf("%d\n",sol[i]);
}