Cod sursa(job #1122073)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 25 februarie 2014 16:03:37
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<fstream>
using namespace std;
int arbi[66000];
void init(int nod, int st, int dr)
{
	int mij;
	if(st==dr)
		arbi[nod]=1;
	else
	{
		mij=(st+dr)/2;
		init(2*nod,st,mij);
		init(2*nod+1,mij+1,dr);
		arbi[nod]=arbi[2*nod]+arbi[2*nod+1];
	}
}
int query(int nod, int st, int dr, int val)
{
	if(st==dr)
		return st;
	int mij=(st+dr)/2;
	if(arbi[2*nod]>=val)
		return query(2*nod, st, mij, val);
	return query(2*nod+1,mij+1,dr,val-arbi[2*nod]);
}
void update(int nod, int st, int dr, int val)
{
	if(st==dr)
		arbi[nod]=0;
	else
	{
		int mij=(st+dr)/2;
		if(arbi[2*nod]>=val)
			update(2*nod, st, mij, val);
		else
			update(2*nod+1,mij+1,dr,val-arbi[2*nod]);
		arbi[nod]=arbi[2*nod]+arbi[2*nod+1];
	}
}
int main()
{
	int n;
	int i;
	int pact=1;
	ifstream f("order.in");
	f>>n;
	f.close();
	init(1,1,n);
	ofstream g("order.out");
	for(i=1;i<=n;i++)
	{
		pact=(pact+i)%arbi[1];
		if(pact==0)
			pact=arbi[1];
		g<<query(1,1,n,pact)<<' ';
		update(1,1,n,pact);
		pact--;
	}
	g<<'\n';
	g.close();
	return 0;
}