Cod sursa(job #773523)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 1 august 2012 22:09:57
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<fstream>
#define lsb(x) (x&(-x))
using namespace std;
int n,i,aib[30003],x,rez,j,ld,qn;
void update(int poz,int val)
{int i;
	for(i=poz;i<=n;i+=lsb(i))
		aib[i]+=val;
}
int query(int poz)
{int i,s=0;
	for(i=poz;i>=1;i-=lsb(i))
		s+=aib[i];
	return s;
}
int bs(int nr)
{int mij,s=1,d=n,val;
	while(s<=d)
	{
		mij=(s+d)/2;
		val=query(mij);
		if(val<nr)s=mij+1;
		if(val>nr)d=mij-1;
		if(val==nr){ rez=mij; d=mij-1; }
	}
	return rez;
}
int main()
{
	ifstream f("order.in");ofstream g("order.out");
	f>>n;
	for(i=1;i<=n;i++)
		update(i,1);
	rez=1;
	for(i=1;i<=n;i++)
	{
		x=rez;
		qn=query(n);
		ld=qn-query(rez);
		if(ld<i)
		{
		 x=i-ld;
		 x=x%qn;
		 if(x==0)x=qn;
		 rez=bs(x);
		}
		else rez=bs(query(x)+i);
		g<<rez<<' ';
		update(rez,-1);
	}
	f.close();g.close();
return 0;}