Cod sursa(job #811153)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 11 noiembrie 2012 16:27:21
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb

#include <cstdio>

const int MAX_SIZE(30001);

int n;
int it [MAX_SIZE << 1];

inline void read (void)
{
	std::freopen("order.in","r",stdin);
	std::scanf("%d",&n);
	std::fclose(stdin);
}

inline int left_son (int index)
{
	return index << 1;
}

inline int right_son (int index)
{
	return (index << 1) + 1;
}

void build (int index, int left, int right)
{
	if (left == right)
	{
		it[index] = 1;
		return;
	}
	int middle((left + right) >> 1);
	build(left_son(index),left,middle);
	build(right_son(index),middle + 1,right);
	it[index] = it[left_son(index)] + it[right_son(index)];
}

void update (int index, int left, int right, int position)
{
	if (left == right)
	{
		it[index] = 0;
		return;
	}
	int middle((left + right) >> 1);
	if (position <= middle)
		update(left_son(index),left,middle,position);
	else
		update(right_son(index),middle + 1,right,position);
	it[index] = it[left_son(index)] + it[right_son(index)];
}

int query (int index, int left, int right, int order)
{
	if (left == right)
		return left;
	int middle((left + right) >> 1);
	if (order <= it[left_son(index)])
		return query(left_son(index),left,middle,order);
	else
		return query(right_son(index),middle + 1,right,order - it[left_son(index)]);
}

inline void print (void)
{
	std::freopen("order.out","w",stdout);
	int child;
	for (int steps(0), position(2) ; steps < n ; ++steps)
	{
		position = (position + steps) % (n - steps);
		if (position)
			child = query(1,1,n,position);
		else
		{
			child = query(1,1,n,n - steps);
			position = 1;
		}
		std::printf("%d ",child);
		update(1,1,n,child);
	}
	std::putchar('\n');
	std::fclose(stdout);
}

int main (void)
{
	read();
	build(1,1,n);
	print();
	return 0;
}