Cod sursa(job #539618)

Utilizator loginLogin Iustin Anca login Data 23 februarie 2011 09:48:48
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
# include <fstream>
# include <iostream>
# define DIM 30003
using namespace std;
int n, v[DIM], a[3*DIM], s[DIM], r;

void read ()
{
	ifstream fin ("schi.in");
	fin>>n;
	for(int i=1;i<=n;++i)
		fin>>v[i];
}

void init (int k, int st, int dr, int p)
{
	if (st==dr)
	{
		a[k]=1;
		return;
	}
	int mij=(st+dr)/2;
	if (p<=mij)
		init(2*k, st, mij, p);
	else
		init(2*k+1, mij+1, dr, p);
	a[k]=a[2*k]+a[2*k+1];
}

void f (int k, int st, int dr, int p)
{
	if (st==dr)
	{
		r=st;
		a[k]=0;
		return;
	}
	int mij=(st+dr)/2;
	if (a[2*k]>=p)
		f(2*k, st, mij, p);
	else
		f(2*k+1, mij+1, dr, p-a[2*k]);
	a[k]=a[2*k]+a[2*k+1];
}

void solve ()
{
	for(int i=1;i<=n;++i)
		init(1, 1, n, i);
	for(int i=n;i;--i)
	{
		f(1, 1, n, v[i]);
		s[r]=i;
	}
}

int main()
{
	read ();
	solve ();
	ofstream fout ("schi.out");
	for(int i=1;i<=n;++i)
		fout<<s[i]<<"\n";
	return 0;
}