Cod sursa(job #549151)

Utilizator bora_marianBora marian bora_marian Data 8 martie 2011 10:28:20
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<fstream>
#define DIM 30005
using namespace std;
int arb[4*DIM],n,poz,a,b,dildau;
int cautare(int nod,int st,int dr,int val);
void update(int nod,int st,int dr,int val);
void caut(int nod,int st,int dr);
int main()
{
	ifstream fin("order.in");
	ofstream fout("order.out");
	fin>>n;
	int i;
	for(int i=1;i<=n;i++)
	{
		poz=i;
		update(1,1,n,1);
	}
	int nr=1;
	for(i=1;i<=n;i++)
	{
	   a=1,b=nr;
	   dildau=0;
	   caut(1,1,n);
	   nr=dildau;
	  // fout<<"dildau"<<dildau<<" ";
	   nr+=i;
	   nr=nr%arb[1];
	   if(nr==0)
	      nr=arb[1];
	   //fout<<nr<<endl;   
	   nr=cautare(1,1,n,nr);
	   fout<<nr<<" ";
	   poz=nr;
	   update(1,1,n,0);   
	
	}
	return 0;
}
void update(int nod,int st,int dr,int val)
{
	if(st==dr)
	{
		arb[nod]=val;
		return ;
	}
	else
	{
	    int mij=(st+dr)/2;
	    if(poz<=mij)
	      update(2*nod,st,mij,val);
	    else
	      update(2*nod+1,mij+1,dr,val);
	}
	arb[nod]=arb[2*nod]+arb[2*nod+1];
}
int cautare(int nod,int st,int dr,int val)
{
	if(st==dr)
		return st;
	int mij=(st+dr)/2;
	if(arb[2*nod]>=val)
	   return cautare(2*nod,st,mij,val);
	val-=arb[2*nod];
	return cautare(2*nod+1,mij+1,dr,val);
}    
void caut(int nod,int st,int dr)
{
	if(st>=a && dr<=b)
	{
		dildau+=arb[nod];
		return ;
	}
	else
	{
		int mij=(st+dr)/2;
		if(a<=mij)
		  caut(2*nod,st,mij);
		if(b>mij)
		  caut(2*nod+1,mij+1,dr);
	 }
}