Cod sursa(job #743021)

Utilizator ioanabIoana Bica ioanab Data 2 mai 2012 21:31:17
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
using namespace std;

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

const int N=30006;

int aib[N],a[N],sol[N],n;

int step(int x)
{
	return x&(-x);
}

int query(int x)
{
	int sum=0;
	
	for(;x;x-=step(x))
		sum+=aib[x];
	
	return sum;
}

void update(int x,int val)
{
	for(;x<=n;x+=step(x))
		aib[x]+=val;
}

int bs(int val)
{
	int i,pas=1<<16;
	
	for(i=0;pas;pas>>=1)
		if(i+pas<=n && aib[i+pas]<val)
		{
			i+=pas;
			val-=aib[i];
		}
	
	return i+1;
}

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