Cod sursa(job #999526)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 20 septembrie 2013 17:12:03
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;
ifstream fi("schi.in");
ofstream fo("schi.out");
int N,i,poz;
int A[30001];
int LOC[30001];
int REZ[30001];

// pe pozitia p se adauga valoarea v, cu consemnare in AIB
void g(int p, int v)
{
	while (p<=N)
	{
		A[p]+=v;
		p=p+((p^(p-1))&p);
	}
}

// calculeaza suma din sir de la pozitia 1 pana la pozitia p, cu ajutorul AIB-ului
int f(int p)
{
	int s;
	s=0;
	while (p>0)
	{
		s=s+A[p];
		p=p-((p^(p-1))&p);
	}
	return s;
}

int bs(int st, int dr, int nr)
{
	int m;
	if (st==dr)
		return st;
	m=(st+dr)/2;
	if (nr<=f(m))
		return bs(st,m,nr);
	else
		return bs(m+1,dr,nr);
}

int main()
{
	fi>>N;
	for (i=1;i<=N;i++)
		fi>>LOC[i];
	for (i=1;i<=N;i++)
		g(i,1);
	for (i=N;i>=1;i--)
	{
		// prin cautare binara se determina
		// pe ce pozitie este gasit cel de-al LOC[i] numar 1
		poz=bs(1,N,LOC[i]);
		g(poz,-1);
		REZ[poz]=i;
	}
	for (i=1;i<=N;i++)
		fo<<REZ[i]<<"\n";
	fi.close();
	fo.close();
	return 0;
}