Cod sursa(job #43668)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 30 martie 2007 12:52:41
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <stdio.h>
#define fin  "order.in"
#define fout "order.out"
#define Nmax 30001
#define Tmax 100000

int N,segm[Tmax],a,b;
int sum;

void init(int nod,int st,int dr) {
int m;
	if (st<=dr) {
		m=(st+dr)/2;
		segm[nod]=dr-st+1;
		if (st!=dr) 
			init(2*nod,st,m);
		init(2*nod+1,m+1,dr);
	}
}

void query(int nod,int st,int dr) {
int m;
	if (a<=st && dr<=b) 
		sum+=segm[nod];
	else {
		if (st>=dr) return ;

		m=(st+dr)/2;
		if (a<=m)
		       query(2*nod,st,m);
		if (b>m)
		       query(2*nod+1,m+1,dr);
	}	

}

int search(int nod,int st,int dr,int val) {
int m,lts,rts;
int i;
	m=(st+dr)/2;
	
	if (segm[nod]==val && st==dr)	// :) tricky one 
		return dr;		//este garantat ca se va ajunge la st==dr deci returna ori st ori dr

	lts=segm[2*nod];
	rts=segm[2*nod+1];
	
	if (lts>=val) 
		return search(2*nod,st,m,val);
	else
		return search(2*nod+1,m+1,dr,val-lts);
	
}

void del(int nod,int st,int dr,int poz) {
int m;
	if (st==dr && st==poz) 
		segm[nod]=0;
	else {
		m=(st+dr)/2;
		if (poz<=m)
			del(2*nod,st,m,poz);
		else
			del(2*nod+1,m+1,dr,poz);
		segm[nod]=segm[2*nod]+segm[2*nod+1];
	}
}

int main() {
int i,j,el,poz,curr;
int left,right;

	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%i",&N);

	init(1,1,N);	//init treeul ca fiind inserat tot

	//del(1,1,N,6);
	//query(1,1,N);
	//fprintf(stderr,"%i\n",search(1,1,N,7));
//	fprintf(stderr,"%i\n",sum); 

	printf("2 ");
	del(1,1,N,2);
	curr=2;

	for (i=2;i<N;++i) {
	//	el=i%(N-i+1);	//aflu pozitia in numaratoare a urm elem
	//	fprintf(stderr,"%i %i\n",curr,el);
	//	if (!el) {
	//		printf("%i ",curr);
	//		del(1,1,N,curr);
	//	}
	//	else {
	//		
			a=1; b=curr; sum=0;
			query(1,1,N);	//aflu suma din intervalul [1,curent-1]
			left=sum;

			a=curr; b=N; sum=0;
			query(1,1,N);	//------------------------ [curent+1,N]
			right=sum;
			
			el=i%segm[1];

			///fprintf(stderr,"%i ",segm[1]);

			if (el==0) el=segm[1];

			//if (curr==3) 
			//	fprintf(stderr,"%i %i %i\n",left,right,el);
			
			if (right>=el) {
			       	sum=left+el;	
				curr=search(1,1,N,left+el);	//este in int dreapta , setez suma left+poz element
			}
			else {
				sum=el-right;
				curr=search(1,1,N,el-right);	//analog
			}
			//fprintf(stderr,"%i\n\n",sum);
			printf("%i ",curr);
			del(1,1,N,curr);
	//	}

		//aflu urmatorul copil de unde incepe numaratoare
	/*	
		a=1; b=curr; sum=0;
		query(1,1,N);
		left=sum;

		a=curr+1; b=N; sum=0;
		query(1,1,N);
		right=sum;	

		if (right==0)  			//este la capat
			curr=search(1,1,N,1);	//caut el de suma 1 din stanga
		else
			curr=search(1,1,N,left+1);	//caut la dreapta suma 1
	*/
	}
	
	curr=search(1,1,N,1);

	if (N==2) curr=1;

	printf("%i\n",curr);

	fclose(stdin); fclose(stdout);

	return 0;
}