Cod sursa(job #1006587)

Utilizator Kira96Denis Mita Kira96 Data 7 octombrie 2013 13:46:15
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream>
#define NM 30100
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int H[4*NM],n,pc,x,cur,i,nc;
void update(int st,int dr,int po,int val)
{
	if(st==dr)
	{
		H[po]=val;
		return;
	}
	int mid=(st+dr)/2;
	if(x<=mid)
		update(st,mid,po*2,val);
	else
		update(mid+1,dr,po*2+1,val);
	H[po]=H[po*2]+H[po*2+1];
}
void find(int st,int dr,int po)
{
	if(st==dr)
	{ 
		x=st;
		return ;
	}
	int mid=(st+dr)>>1;
	if(pc<=H[po*2])
		find(st,mid,po*2);
	else
	{
		pc-=H[po*2];
		find(mid+1,dr,po*2+1);
	}
	return ;
}
int main ()
{
	f>>n;
	for(x=1;x<=n;++x) update(1,n,1,1);
	cur=2;
	for(i=1;i<=n;++i)
	{
		nc=H[1];
		pc=cur+i-1;
		while(pc>nc)
			pc-=nc;
		cur=pc;
		find(1,n,1);
		update(1,n,1,0);
		g<<x<<" ";
	}
	return 0;
}