Cod sursa(job #567706)

Utilizator HoriaClementHoriaC HoriaClement Data 30 martie 2011 13:25:43
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<fstream>

using namespace std;

ifstream in("order.in");
ofstream out("order.out");

int n,arb[120005],x,poz;


void update(int nod,int p,int u,int x,int y)
{
	int m;
	if(p==u)
	{
		arb[nod]+=y;
		return;
	}
	m=(p+u)>>1;
	if(x<=m)
		update(nod*2,p,m,x,y);
	else
		update(nod*2+1,m+1,u,x,y);
	arb[nod]=arb[2*nod]+arb[2*nod+1];
}

int cauta(int nod,int p,int u,int x,int y)
{
	int m,a,b;
	if(x<=p && u<=y)
		return arb[nod];
	if(x>y)
		return 0;
	m=(p+u)>>1;
	if(x<=m)
		a=cauta(nod*2,p,m,x,y);
	if(m<y)
		b=cauta(nod*2+1,u,m+1,x,y);
	return a+b;
}
	
int find(int nod,int p,int u,int y)
{
	int m;
	if(p==u)
		return p;
	m=(p+u)>>1;
	if(arb[2*nod]<y)
		return find(2*nod+1,m+1,u,y-arb[2*nod]);
	else
		return find(2*nod,p,m,y);
}
	
void rez()
{
	in>>n;
	for(int i=1;i<=n;++i)
		update(1,1,n,i,1);
	update(1,1,n,2,-1);
	out<<"2";
	poz=2;
	for(int i=2;i<=n;++i)
	{
		x=cauta(1,1,n-1,i,poz-1);
		x=(x+i)%arb[1];
		if(x==0)
			x=arb[1];
		poz=find(1,1,n,x);
		printf("%d",poz-1);
		update(1,1,n-1,n,poz-1);
	}
	printf("\n");
}

int main()
{
	rez();
	return 0;
}