Cod sursa(job #858313)

Utilizator deea101Andreea deea101 Data 18 ianuarie 2013 19:43:00
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,a[30000],b[30000],t[120002];
void update(int i, int nod, int val, int st, int dr)
{
	if(st==dr) t[i]=val;
	else
	{
		int mij=(st+dr)/2;
		if(nod<=mij) update(2*i,nod,val,st,mij);
		else update(2*i+1,nod,val,mij+1,dr);
		
		t[i]=t[2*i]+t[2*i+1];
	}
}
int query(int i, int val, int st, int dr)
{
	if(st==dr) 
	{
		t[i]=0;
		return st;
	}
	else
	{
		int mij=(st+dr)/2,x;
		if(val<=t[2*i]) x=query(2*i,val,st,mij);
		else x=query(2*i+1,val-t[2*i],mij+1,dr);
		
		t[i]=t[2*i]+t[2*i+1];
		return x;
	}
}

int main()
{
	f>>n;
	int i;
	for(i=1;i<=n;i++)
	{
		f>>a[i];
		update(1,i,1,1,n);
	}
	for(i=n;i;i--)
		b[query(1,a[i],1,n)]=i;
	for(i=1;i<=n;i++)
		g<<b[i]<<'\n';
}