Cod sursa(job #43676)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 30 martie 2007 12:58:30
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 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
	
	printf("2 ");	//scoatem pe 2
	del(1,1,N,2);
	curr=2;

	for (i=2;i<N;++i) {
		a=1; b=curr-1; 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;
			
		el=i%segm[1];

		if (el==0) el=segm[1];
		
		if (right>=el) 
		       	curr=search(1,1,N,left+el);	//este in int dreapta , setez suma left+poz element
		
		else 
			curr=search(1,1,N,el-right);	//analog
			
		printf("%i ",curr);
		del(1,1,N,curr);
	}
	
	curr=search(1,1,N,1);

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

	fclose(stdin); fclose(stdout);

	return 0;
}