Cod sursa(job #1122007)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 25 februarie 2014 15:19:47
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<cstdio>
using namespace std;
int pozpar[30001];
int arbi[66000];
int rez[30001];
void initial(int nod, int st, int dr)
{
	int mij;
	if(st==dr)
		arbi[nod]=1;
	else
	{
		mij=(st+dr)/2;
		initial(2*nod,st,mij);
		initial(2*nod+1,mij+1,dr);
		arbi[nod]=arbi[2*nod]+arbi[2*nod+1];
	}
}
int query(int nod, int st, int dr, int val)
{
	int mij;
	if(st==dr)
		return st;
	else
	{
		mij=(st+dr)/2;
		if(arbi[2*nod]>=val)
			return query(2*nod,st,mij,val);
		else
			return query(2*nod+1,mij+1,dr,val-arbi[2*nod]);
	}
}
void update(int nod, int st, int dr, int val)
{
	int mij;
	if(st==dr)
		arbi[nod]=0;
	else
	{
		mij=(st+dr)/2;
		if(arbi[2*nod]>=val)
			update(2*nod,st,mij,val);
		else
			update(2*nod+1,mij+1,dr,val-arbi[2*nod]);
		arbi[nod]=arbi[2*nod]+arbi[2*nod+1];
	}
}
int main()
{
	int n;
	int i;
	int poz;
	freopen("schi.in","r",stdin);
	scanf("%d\n",&n);
	for(i=1;i<=n;i++)
		scanf("%d\n",&pozpar[i]);
	fclose(stdin);
	initial(1,1,n);
	for(i=n;i>0;i--)
	{
		poz=query(1,1,n,pozpar[i]);
		rez[poz]=i;
		update(1,1,n,pozpar[i]);
	}
	freopen("schi.out","w",stdout);
	for(i=1;i<=n;i++)
		printf("%d\n",rez[i]);
	fclose(stdin);
	return 0;
}