Cod sursa(job #43335)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 29 martie 2007 23:22:32
Problema Order Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 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

	curr=1;		//repr poz unde se opreste numaratoarea
	
	a=5; b=16; sum=0;
	//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=3;

	for (i=2;i<N;++i) {
		el=i%(N-i+1)-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+1; b=N; sum=0;
			query(1,1,N);	//------------------------ [curent+1,N]
			right=sum;

			if (right>=el) {
			       	sum=left+el-1;	
				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 %i\n\n",left,right);
			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
	
	}

	if (N==2) curr=1;

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

	fclose(stdin); fclose(stdout);

	return 0;
}