Cod sursa(job #614509)

Utilizator ChallengeMurtaza Alexandru Challenge Data 6 octombrie 2011 18:59:10
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>

using namespace std;

const char InFile[]="order.in";
const char OutFile[]="order.out";
const int MaxN=30111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,pos,sol,aint[MaxN<<2];

void update(int nod, int st, int dr)
{
	if(st==dr)
	{
		aint[nod]=0;
		sol=st;
		return;
	}
	
	int l=nod<<1;
	int mid=st+((dr-st)>>1);
	if(pos<=aint[l])
	{
		update(l,st,mid);
	}
	else
	{
		pos-=aint[l];
		update(l+1,mid+1,dr);
	}

	aint[nod]=aint[l]+aint[l+1];
}

void init(int nod, int st, int dr)
{
	aint[nod]=dr-st+1;
	if(st==dr)
	{
		return;
	}

	int mid=st+((dr-st)>>1);
	nod<<=1;
	init(nod,st,mid);
	init(nod+1,mid+1,dr);
}

int main()
{
	fin>>N;
	fin.close();

	init(1,1,N);
	int tpos=1;
	for(register int i=1;i<=N;++i,--tpos)
	{
		tpos+=i;
		tpos=(tpos-1)%(N-i+1)+1;
		pos=tpos;
		update(1,1,N);
		fout<<sol<<" ";
	}
	fout.close();
	return 0;
}