Cod sursa(job #772761)

Utilizator starduststardust stardust Data 30 iulie 2012 18:03:00
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<fstream>
#define maxn 30010


using namespace std;

struct {int poz,sum;} arb[4*maxn+5];

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

int val,poz,n,s,pozitie,ans,j;

void update(int nod,int left,int right)
{
	if(left==right)
	{
		arb[nod].poz=poz;
		arb[nod].sum=val;
		return;
	}
	int mid=(left+right)/2;
	if(poz<=mid) update(2*nod,left,mid);
	else update(2*nod+1,mid+1,right);
	
	arb[nod].sum=arb[2*nod].sum+arb[2*nod+1].sum;
}

void findpoz(int nod,int left,int right)
{
	if(left==right)
	{
		poz=left;
		ans=arb[nod].poz;
		return;
	}
	int mid=(left+right)/2;
	if(val<=arb[2*nod].sum) findpoz(2*nod,left,mid);
	else
	{
		val-=arb[2*nod].sum;
        findpoz(2*nod+1,mid+1,right);
    }
}	

void query(int nod,int left,int right,int i,int j)
{
	if(i<=left && right<=j)
	{
		s+=arb[nod].sum;
		return;
	}
	int mid=(left+right)/2;
	if(i<=mid) query(2*nod,left,mid,i,j);
	if(j>mid) query(2*nod+1,mid+1,right,i,j);
}

void read()
{
	in>>n;
	for(int i=1;i<=n;i++)
	{
		poz=i;
		val=1;
		update(1,1,n);
	}
	pozitie=1;
	for(int i=1;i<=n;i++)
	{
		s=0;
		query(1,1,n,1,n);
		j=i;
		while(j>s) j-=s;
		s=0;
		query(1,1,n,pozitie+1,n); // cate pozitii mai am de la elementul curent in colo
		
		if(s<=j) //daca am mai putine decat trebuie sa sterg 
		{
			val=j-s; // o iau de la capat si il sterg pe al i-s - lea 
			if(val==0) val=1;
			findpoz(1,1,n);
			val=0;
			update(1,1,n);
			pozitie=poz;
		}
		else // daca am suficiente in intervalul pozitie+1
		{
			s=0;
			query(1,1,n,1,pozitie);
			val=j+s;
			findpoz(1,1,n);
			val=0;
			update(1,1,n);
			pozitie=poz;
		}
		out<<ans<<" ";
	}
}
			
int main()
{
	read();
}