Cod sursa(job #1253472)

Utilizator CostinVFMI CostinVictorGabriel CostinV Data 1 noiembrie 2014 13:19:10
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>

using namespace std;

int arb[1000000], n;

void build_arb (int i, int st, int dr)
{
	int m = (st+dr)/2; 
	
	if (st!=dr)
	{
		build_arb (i*2, st, m);
		build_arb (i*2+1, m+1, dr);
		arb[i] = arb[i*2] + arb[i*2+1];
	}
	else
	{
		arb[i] = 1;
	}
}

int query (int st, int dr, int i, int el)
{
	int m = (st+dr)/2;

	if (st==dr)
		return st;
	if (el > arb[i*2])
		return query (m+1, dr, i*2+1, el-arb[i*2]);
	else
		return query (st, m, i*2, el);
}

void update (int st, int dr, int i, int poz)
{
	int m = (st+dr)/2;
	
	if (st==dr)
	{
		arb[i] = 0;
		return;
	}
	
	if (poz <= m)
		update (st, m, i*2, poz);
	else
		update (m+1, dr, i*2+1, poz);

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

int main ()
{
	ifstream in ("order.in");
	ofstream out ("order.out");

	in>>n;

	build_arb (1, 1, n);
	
	int r = n, i=2, nr=1, el;

	while (r)
	{
		i = (i+nr-1)%r;
		
		if(i==0)
			i=r;

		el = query (1, n, 1, i);
		out<<el<<" ";
		update (1, n, 1, el);
		r--;
		nr++;
	}

	return 0;
}