Cod sursa(job #539620)

Utilizator bora_marianBora marian bora_marian Data 23 februarie 2011 09:50:42
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#define DIM 30003
using namespace std;
int arb[3*DIM],n,v[DIM],poz,sol[DIM];
void update(int nod,int st,int dr,int val);
 int cauta(int nod,int st,int dr,int val);
int main()
{
	ifstream fin("schi.in");
	ofstream fout("schi.out");
	fin>>n;
	int i;
	for(i=1;i<=n;i++)
	{
		poz=i;
		fin>>v[i];
		update(1,1,n,1);
	}  
	for(i=n;i>=1;i--)
	{
		poz=cauta(1,1,n,v[i]);
		sol[cauta(1,1,n,v[i])]=i;
		update(1,1,n,0);
	}
	for(i=1;i<=n;i++)
	   fout<<sol[i]<<"\n";
	return 0;
   }
void update(int nod,int st,int dr,int val)
{
	if(st==dr)
	{
		arb[nod]=val;
		return ;
	}
	else
	{
		int mij=(st+dr)/2;
		if(poz<=mij)
		  update(2*nod,st,mij,val);
		else 
		  update(2*nod+1,mij+1,dr,val);  
	 }
	 arb[nod]=arb[2*nod]+arb[2*nod+1];
 }
 int cauta(int nod,int st,int dr,int val)
 {
 	if(st==dr)
 	  return st;
 	int mij=(st+dr)/2;
 	if(arb[2*nod]>=val)
 	    return cauta(2*nod,st,mij,val);
 	val-=arb[2*nod];
 	return cauta(2*nod+1,mij+1,dr,val);
}