Cod sursa(job #415542)

Utilizator otilia_sOtilia Stretcu otilia_s Data 11 martie 2010 15:21:18
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#define NMAX 30010
using namespace std;
short ad[NMAX],aib[NMAX],n,final[NMAX];


void adauga(int x)
{
	for (;x<=n; x+=(x^(x-1))&x)
		aib[x]+=1;
}

void sterge(int x)
{
	for (;x<=n; x+=(x^(x-1))&x)
		aib[x]-=1;
}

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

void cauta(int &poz, int x)
{
	int st=1,dr=n;
	while (st<=dr)
	{
		int mij=(st+dr)>>1;
		int cate=query(mij);
		if (cate>=x) { poz=mij; dr=mij-1;}
		   else { st=mij+1;}		
	}
}

int main()
{
	ifstream fin("schi.in");
	int i,poz;
	fin>>n;
	for (i=1;i<=n;++i) 
		{
			fin>>ad[i];
			adauga(i);
		}
	fin.close();
	
	for (i=n;i;--i)
	{ 
		cauta(poz,ad[i]);		
		final[poz]=i;
		sterge(poz);
	}
	
	ofstream fout("schi.out");
	for (i=1;i<=n;++i)
		fout<<final[i]<<"\n";
	fout.close();
	return 0;
}