Cod sursa(job #415507)

Utilizator otilia_sOtilia Stretcu otilia_s Data 11 martie 2010 14:29:21
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#define NMAX 30010
using namespace std;
short ad[NMAX],poz[NMAX],S[NMAX*5+1];
short g,gasit,x;

void gaseste(short nod, short st, short dr)
{
	if (st==dr) 
		{
		  S[nod]=1; ++g; gasit=st;
		}
		else
		{
			short mij=(st+dr)>>1;
			short rs=mij-st+1-S[nod<<1]; //ramase in st
			if (g+rs<x)  //daca in stanga sunt mai putine elem ramase decat am nevoie
				{ 
					g+=rs; //le adaug;
					gaseste((nod<<1)+1,mij+1,dr); //caut in dr
				}
			   else gaseste(nod<<1,st,mij);			
			S[nod]=S[nod<<1]+S[(nod<<1)+1];
		}
}

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