Cod sursa(job #976186)

Utilizator cont_de_testeCont Teste cont_de_teste Data 22 iulie 2013 18:17:42
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <fstream>
using namespace std;

#ifdef INFOARENA
	ifstream fin("order.in");
	ofstream fout("order.out");
	#define cin fin
	#define cout fout
#endif

const int maxn = 30100;
int n;
int aint[maxn * 2 + 10000];

void build(int node, int left, int right)
{
	aint[node] = right - left + 1;
	if (left >= right)
		return ;
	int middle = (left + right) >> 1;
	build(node * 2, left, middle);
	build(node * 2 + 1, middle + 1, right);
}
void update(int node, int left, int right, int position, int value)
{
	if (left >= right)
	{
		aint[node] += value;
		return ;
	}
	int middle = (left + right) >> 1;
	if (position <= middle) update(node * 2, left, middle, position, value);
	else update(node * 2 + 1, middle + 1, right, position, value);
}
inline int query(int node, int left, int right, int leftbound, int rightbound)
{
	if (leftbound > rightbound) return 0;
	if (leftbound <= left && right <= rightbound)
		return aint[node];
	int middle = (left + right) >> 1;
	int result = 0;
	if (leftbound <= middle) result += query(node * 2, left, middle, leftbound, rightbound);
	if (middle + 1 <= rightbound) result += query(node * 2 + 1, middle + 1, right, leftbound, rightbound);
	return result;
}
inline int src(int node, int left, int right, int sum, int limit)
{
	if (left >= right)
	{
		if (sum + aint[node] == limit) return left;
		return left + 1;
	}
	int middle = (left + right) >> 1;
	if (sum + aint[node * 2] >= limit)
		return src(node * 2, left, middle, sum, limit);
	else
		return src(node * 2 + 1, middle + 1, right, sum + aint[node * 2], limit);
}

int main()
{
	cin >> n;
	build(1, 1, n);
	
	for (int i = 1, le = n, rem = 1; i <= n; i++, le--)
	{
		int hm = i % le, foo = query(1, 1, n, rem + 1, n);
		if (hm == 0) hm = le;
		
		if (foo >= hm)
		{
			int add = query(1, 1, n, 1, rem);
			rem = src(1, 1, n, -add, hm);
		}
		else
		{
			hm -= foo;
			rem = src(1, 1, n, 0, hm);
		}
		cout << rem << ' ';
		update(1, 1, n, rem, -1);
	}
}