Cod sursa(job #1448148)

Utilizator IoanaaChriistinaaPascal Ioana-Cristina IoanaaChriistinaa Data 6 iunie 2015 12:56:27
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<fstream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int aib[30010],v[30010],vc[30010],n;
int suma(int poz)
{
	int s=0;
	for(;poz>0;poz-=((poz&(poz-1))^poz)
		s+=aib[poz];
	return s;
}
int adg(int poz, int val)
{
	for(;poz<=n;poz+=((poz&(poz-1))^poz))
		aib[poz]+=val;
}
int main()
{
	int i, st,dr, m,mij,x;
	in>>n;
	for(i=1;i<=n;i++)
		in>>v[i],adg(i,1);
	for(i=n;i>=1;i--)
	{
		st=1,dr=n;
		m=1000000;
		while(st<=dr)
		{
			mij=(st+dr)/2;
			x=sum(mij);
			if(x==v[i]&&aib[mij]!=0&&mij<m)
				m=mij;
			if(v[i]<=x)
				dr=mij-1;
			else st=mij+1;
		}
		vc[m]=i;
		adg(m,-1);
	}
	for(i=1;i<=n;i++)
		out<<vc[i];
	return 0;
}