Cod sursa(job #227494)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 4 decembrie 2008 19:53:32
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>

int n, arb[100005], nr, nn, val, pos, x, poz;

void update(int nod, int st, int dr)
{
	int m = (st + dr) / 2;
	if (st == dr)
	{
		arb[nod] = val;
	}
	else
	{
		if (pos <= m) update(2 * nod, st, m);
		else update(2 * nod + 1, m + 1, dr);

		arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
	}
}

void query(int nod, int st, int dr, int l, int r)
{
	int m = (st + dr) / 2;
	if (l <= st && dr <= r)
	{
		x += arb[nod];
	}
	else
	{
		if (l <= m) query(2 * nod, st, m, l, r);
		if (r >= m + 1) query(2 * nod + 1, m + 1, dr, l, r);
	}
}

void find(int nod, int st, int dr, int x)
{
	int m = (st + dr) / 2;
	if (arb[nod] == x && st == dr)
	{
		printf("%d ",st);
		arb[nod] = 0;
		poz = st;
	}
	else
	{
		if (x <= arb[2 * nod]) find(2 * nod, st, m, x);
		else find(2 * nod + 1, m + 1, dr, x - arb[2 * nod]);

		arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
	}
}



int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);

	scanf("%d",&n);

	val = 1;
	int i;
	for (i = 1; i <= n; i++) 
	{
		pos = i;
		update(1,1,n);
	}

	int k;
	
	printf("2 "); val = 0; pos = 2;
	update(1,1,n);
	poz = 2;
	for (i = 2; i <= n; i++)
	{
		x = 0;
		query(1,1,n,1,poz);
		k = x + i;
		if (k > n - i + 1) k %= (n - i + 1);
		if (!k) k = n - i + 1;
	
		find(1,1,n,k);
	}
	return 0;
}