Cod sursa(job #333679)

Utilizator cezarbotolanbotolan cezar cezarbotolan Data 23 iulie 2009 15:30:09
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>

#define file_in "order.in"
#define file_out "order.out"

#define Nmax 120010

int n,poz,sol;
int ai[Nmax];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
}

void update(int nod, int st, int dr, int poz, int x)
{
	if (st==dr)
	{
		ai[nod]=x;
		return ;
	}
	
	int mij=(st+dr)>>1;
	if (poz<=mij)
		update(2*nod,st,mij,poz,x);
	else
		update(2*nod+1,mij+1,dr,poz,x);
	ai[nod]=ai[2*nod]+ai[2*nod+1];
}

int query(int nod, int st, int dr, int poz)
{
	if (st==dr)
		return st;
	
	int mij=(st+dr)>>1;
	
	if (poz<=ai[2*nod])
		return query(2*nod,st,mij,poz);
	else
		return query(2*nod+1,mij+1,dr,poz-ai[2*nod]);
}

int main()
{
	int i;
	
	citire();
		
	for (i=1;i<=n;++i)
		 update(1,1,n,i,1);
	
	/*for (i=1;i<=n;++i)
		 printf("%d ",ai[i]);*/
	
	poz=1;
	
	for (i=1;i<=n;++i)
	{
		poz=(poz+i)%ai[1];
		if (poz==0) poz=ai[1];
		sol=query(1,1,n,poz);
		printf("%d ", sol);
		update(1,1,n,sol,0);
		poz-=1;
		if (poz==0) poz=ai[0];
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}