Cod sursa(job #180)

Utilizator MariusMarius Stroe Marius Data 6 decembrie 2006 00:08:34
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
using namespace std;

const char iname[] = "order.in";
const char oname[] = "order.out";

#define MAX_N 30001

#define left  ((n) * 2)
#define right ((n) * 2 + 1)
#define mid   ((l + r) / 2)

int T[MAX_N * 3];


void build_tree(int n, int l, int r)
{
	T[n] = r-l+1;
	if (l == r)
		return;
	build_tree(left, l, mid);
	build_tree(right, mid + 1, r);
}

void update(int n, int l, int r, int k)
{
	if (l == r) {
		T[n] = 0;
		return  ;
	}
	if (k <= T[left])
		update(left, l, mid, k);
	else
		update(right, mid + 1, r, k - T[left]);
	T[n] = T[left] + T[right];
}

int query(int n, int l, int r, int k)
{
	if (l == r)
		return l;
	if (k <= T[left])
		return  query(left, l, mid, k);
	return  query(right, mid + 1, r, k - T[left]);
}

int main(void)
{
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	int n;
	int k;
	int stp;

	scanf("%d", &n);
	
	build_tree(1, 1, n);

	for (k = 2, stp = 0; stp < n; ++stp) {
		k = k + (stp % T[1]);
		if (k > T[1])
			k -= T[1];
		printf("%d ", query(1, 1, n, k));
		update(1, 1, n, k);
		if (k > T[1])
			k = 1;
	}

	return 0;
}