Cod sursa(job #755779)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 7 iunie 2012 10:52:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream>
using namespace std;
int n,v[30100],AIB[30100],sol[30100];
bool ocupat[30100];

inline void Update(int poz,int x)
{
	while(poz<=n)
	{
		AIB[poz]+=x;
		poz+=(poz & -poz);
	}
}

inline int Query(int poz)
{
	int sum=0;
	while(poz)
	{
		sum+=AIB[poz];
		poz-=(poz & -poz);
	}
	return sum;
}

inline int CautareBinara(int x)
{
	int st,dr,mij,nr;
	st=1;
	dr=n;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		nr=Query(mij);
		if(!ocupat[mij] && nr==x)
			return mij;
		if(nr<x)
			st=mij+1;
		else
			dr=mij-1;
	}
	return 0;
}

int main()
{
	int i,loc;
	ifstream fin("schi.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
	
	for(i=1;i<=n;i++)
		Update(i,1);
	for(i=n;i>0;i--)
	{
		loc=CautareBinara(v[i]);
		sol[loc]=i;
		ocupat[loc]=true;
		Update(loc,-1);
	}
	
	ofstream fout("schi.out");
	for(i=1;i<=n;i++)
		fout<<sol[i]<<"\n";
	fout.close();
	return 0;
}