Cod sursa(job #544321)

Utilizator ChallengeMurtaza Alexandru Challenge Data 1 martie 2011 13:42:37
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>

using namespace std;

const char InFile[]="schi.in";
const char OutFile[]="schi.out";
const int MaxN=30111;
const int aint_SIZE=1<<18;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,v[MaxN],aint[aint_SIZE],sol[MaxN],vsol[MaxN];
int query_result;
int update_pos,update_val;

void query(int st,int dr,int nod,int pos)
{
	if(st==dr)
	{
		query_result=st;
		return;
	}
	int l=nod<<1;
	int m=st+((dr-st)>>1);
	if(pos<=aint[l])
	{
		query(st,m,l,pos);
	}
	else
	{
		query(m+1,dr,l|1,pos-aint[l]);
	}
}

void update(int st,int dr,int nod)
{
	if(st==dr)
	{
		aint[nod]=update_val;
		return;
	}
	int l=nod<<1;
	int m=st+((dr-st)>>1);
	if(update_pos<=m)
	{
		update(st,m,l);
	}
	else
	{
		update(m+1,dr,l|1);
	}
	aint[nod]=aint[l]+aint[l|1];
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>v[i];
		update_pos=i;
		update_val=1;
		update(1,N,1);
	}
	fin.close();
	
	for(register int i=N;i>=1;--i)
	{
		query_result=0;
		query(1,N,1,v[i]);
		vsol[i]=query_result;
		update_val=0;
		update_pos=query_result;
		update(1,N,1);
	}
	
	for(register int i=1;i<=N;++i)
	{
		sol[vsol[i]]=i;
	}
	
	for(register int i=1;i<=N;++i)
	{
		fout<<sol[i]<<"\n";
	}
	fout.close();
	return 0;
}