Cod sursa(job #432868)

Utilizator vladbBogolin Vlad vladb Data 2 aprilie 2010 20:56:11
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

int n;
int a[70000];

void constr(int st,int dr,int nod)
{	a[nod]=dr-st+1;
	if(st==dr) return;
	int mij=(st+dr)/2;
	constr(st,mij,2*nod);
	constr(mij+1,dr,2*nod+1);
}

int cauta(int st,int dr,int nod,int val)
{	if(st==dr) return st;
	int mij=(st+dr)/2;
	if(a[2*nod]>=val)
		return cauta(st,mij,2*nod,val);
	else return cauta(mij+1,dr,2*nod+1,val-a[2*nod]);
}

void actualizeaza(int st,int dr,int nod,int val)
{	if(st==dr)
	{	a[nod]=0;
		return;
	}	
	int mij=(st+dr)/2;
	if(mij>=val) actualizeaza(st,mij,2*nod,val);
	else actualizeaza(mij+1,dr,2*nod+1,val);
	a[nod]=a[2*nod]+a[2*nod+1];
}

int main()
{	int k=2,p,i;
	fin>>n;
	constr(1,n,1);
	for(i=1;i<=n;i++)
	{	k+=i%a[1]-1;
		if(k>a[1]) k-=a[1];
		if(k==0) k=a[1];
		p=cauta(1,n,1,k);
		actualizeaza(1,n,1,p);
		fout<<p<<" ";
	}
	fin.close();
	fout.close();
	return 0;
}