Cod sursa(job #787366)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 13 septembrie 2012 11:23:00
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
using namespace std;
int n,aib[30100];

inline void Update(int poz,int val)
{
	while(poz<=n)
	{
		aib[poz]+=val;
		poz+=(poz & -poz);
	}
}

inline int Query(int poz)
{
	int sum=0;
	while(poz>0)
	{
		sum+=aib[poz];
		poz-=(poz & -poz);
	}
	return sum;
}

inline int CautareBinara(int val)
{
	int st,dr,mij,x,rez;
	st=1;
	dr=n;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		x=Query(mij);
		if(x>=val)
		{
			rez=mij;
			dr=mij-1;
		}
		else
			st=mij+1;
	}
	return rez;
}

int main()
{
	int i,next,now,total,inc;
	ifstream fin("order.in");
	fin>>n;
	fin.close();
	
	for(i=1;i<=n;i++)
		Update(i,1);
	ofstream fout("order.out");
	now=1;
	for(i=1;i<=n;i++)
	{
		next=now;
		total=Query(n);
		inc=Query(now);
		if(total-inc>=i)
			next=inc+i;
		else
		{
			next=i-(total-inc);
			next=next%total;
			if(next==0)
				next=total;
		}
		now=CautareBinara(next);
		fout<<now<<' ';
		Update(now,-1);
	}
	fout<<"\n";
	fout.close();
	return 0;
}