Cod sursa(job #976000)

Utilizator cont_de_testeCont Teste cont_de_teste Data 22 iulie 2013 11:42:53
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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 aib[maxn];

inline void update(int position, int value)
{
	for (int i = position; i <= n; i = (i | (i - 1)) + 1)
		aib[i] += value;
}
inline int start_query(int position)
{
	int res = 0;
	for (int i = position; i >= 1; i = i & (i - 1))
		res += aib[i];
	return res;
}
inline int query(int start, int finish)
{
	return start_query(finish) - start_query(start - 1);
}

inline int binsrc(int elements, int add)
{
	int i = 0, cnt = 1 << 16, sum = -add;
	for (; cnt; cnt >>= 1)
		if (i + cnt <= n && sum + aib[i + cnt] < elements)
			sum += aib[i += cnt];
	return i + 1;
}

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