Cod sursa(job #856804)

Utilizator ioanapopaPopa Ioana ioanapopa Data 16 ianuarie 2013 22:56:06
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<cstdio>
#include<cstdlib>
#define q 100000
using namespace std;

int Arbore[q],pozitie,elem;

inline void make(int left,int right,int nod)
{
	if(right==left)	
		{
			Arbore[nod]=elem;
			return;
		}
	
		int	mij=(right+left)/2;
		int aux = 2*nod;
			if(pozitie <= mij)	
			make(left,mij,aux);
			else
			make(mij+1,right,aux+1);
		
	Arbore[nod]=Arbore[aux]+Arbore[aux+1];
}

inline void interogare(int nod,int left, int right,int s)
{
	if( right==left)
	{
		pozitie=left;
		return;
	}
		int aux = 2*nod;
		int	mij=(left+right)/2;
			if(Arbore[aux]>=s) 
				interogare(aux,left,mij,s);
			else  
				interogare(aux+1,mij+1,right,s-Arbore[aux]);
		
}
int main()
{
	int n,urmator;

	freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
	scanf("%d",&n);
	elem=1;
	for(int i=1;i<=n;i++)
		{	pozitie=i;
			
			make(1,n,1);
		}
	elem=0;				//in arbore punem 0 daca a fost scosa frunza
	urmator=1;			//pornim de la primul element
	for(int i=1;i<=n;++i)
		{
			urmator=(urmator+i+Arbore[1])%Arbore[1];
			if(urmator==0)
				urmator=Arbore[1];
			interogare(1,1,n,urmator);
			make(1,n,1);
			printf("%d ",pozitie);
			--urmator;
			}
		
		return 0;
	}