Cod sursa(job #482905)

Utilizator ilincaSorescu Ilinca ilinca Data 5 septembrie 2010 23:59:56
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>

#define nmax 30005
#define pmax nmax<<2

int n, s, x=1, k=2, a [pmax];


void init (int nod, int st, int dr)
{
	if (st == dr)
	{
		a [nod]=1;
		return;
	}
	int m=(st+dr)>>1;
	init (nod<<1, st, m);
	init ((nod<<1)+1, m+1, dr);
	a [nod]=a [nod<<1]+a [(nod<<1)+1];
}

int query (int nod, int st, int dr)
{
	if (st == dr) return st;
	int m=(st+dr)>>1;
	if (s+a [nod<<1] >= k) query (nod<<1, st, m);
	else
	{
		s+=a [nod<<1];
		query ((nod<<1)+1, m+1, dr);
	}
}

void update (int nod, int st, int dr)
{
	if (st == dr)
	{
		a [nod]=0;
		return;
	}
	int m=(st+dr)>>1;
	if (m >= x) update (nod<<1, st, m);
	else update ((nod<<1)+1, m+1, dr);
	a [nod]=a [nod<<1]+a [(nod<<1)+1];
}

int main ()
{
	freopen ("order.in", "r", stdin);
	freopen ("order.out", "w", stdout);
	scanf ("%d", &n);
	init (1, 1, n);
	int i;
	for (i=1; i <= n; ++i)
	{
		k=(k+i-1)%a [1];
		if (k == 0) k=a [1];
		s=0;
		x=query (1, 1, n);
		update (1, 1, n); 
		printf ("%d ", x);
	}
	return 0;
}