Cod sursa(job #571196)

Utilizator mihai995mihai995 mihai995 Data 4 aprilie 2011 10:09:09
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
using namespace std;

const int N=30001;
int v[3*N],a[N],ans[N],n,pmax,val;

ifstream in("schi.in");
ofstream out("schi.out");

void update(int poz,int st,int dr,int x,int val)
{
	if (st==dr)
	{
		v[poz]=val;
		return;
	}
	int m=(st+dr)>>1;
	if (m>=x)
		update(poz<<1,st,m,x,val);
	else
		update((poz<<1)+1,m+1,dr,x,val);
	v[poz]=v[poz<<1]+v[(poz<<1)+1];
}

void query(int poz,int st,int dr)
{
	if (v[poz]<=val)
	{
		val-=v[poz];
		pmax=max(pmax,dr);
		return;
	}
	int m=(st+dr)>>1;
	if (v[poz<<1]>val)
		query(poz<<1,st,m);
	else
	{
		val-=v[poz<<1];
		pmax=max(pmax,m);
		query((poz<<1)+1,m+1,dr);
	}
}

int greedy(int V)
{
	pmax=0;
	val=V-1;
	query(1,1,n);
	return pmax;
}

int main()
{
	int i,x;
	in>>n;
	for (i=1;i<=n;i++)
		in>>a[i];
	for (i=1;i<=n;i++)
		update(1,1,n,i,1);
	for (i=n;i;i--)
	{
		x=greedy(a[i]);
		ans[x]=i;
		update(1,1,n,x,0);
	}
	for (i=1;i<=n;i++)
		out<<ans[i]<<"\n";
	return 0;
}