Cod sursa(job #606939)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 10 august 2011 14:37:52
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>

int heap[120000];
int retC;
int nrC;

void ConstruiesteHeap(int nod,int left,int right)
{
	if(left == right){
		heap[nod] = 1 ;
		return;
	}

	int mid = (left+right)/2;
	ConstruiesteHeap(2*nod,left,mid);
	ConstruiesteHeap(2*nod+1,mid+1,right);
	heap[nod] = heap[2*nod]+heap[2*nod+1];
}

void AdaugaEliminare(int nod,int left,int right,int pos) // seteaza copilul pos ca fiind eliminat
{
	if(left == right){
		heap[nod] = 0;
		return;
	}

	int mid = (left+right)/2;
	int aux = 2*nod;
	if(pos<=mid)
		AdaugaEliminare(aux,left,mid,pos);
	else{
		nrC += heap[aux];
		AdaugaEliminare(aux+1,mid+1,right,pos);
	}
	heap[nod] = heap[aux]+heap[aux+1];
}

int CatiCopii(int nod,int left,int right,int a,int b) // left right = intervalul nodului curent ; a,b intervalul de interogat
{
	if(a==left && b==right)
		return heap[nod];

	int mid = (left+right)/2;
	if(b<=mid)
		return CatiCopii(2*nod,left,mid,a,b);
	else if(a>mid)
		return CatiCopii(2*nod+1,mid+1,right,a,b);
	else
		return CatiCopii(2*nod,left,mid,a,mid)+CatiCopii(2*nod+1,mid+1,right,mid+1,b);
}// intoarce numarul de copii din intervalul [a,b] ( copii neeliminati ) 


void CautaCopil(int nod,int left,int right,int val) // cauta copilul c , prezent in intervalul (left,right),
													// pentru care in intervalul (left,c) se afla val copii activi
{
	if(left == right){
		retC = left;
		return;
	}
	int aux = 2*nod;
	if(heap[aux] < val) // daca in stanga sunt mai putini , caut in dreapta , urmarind sa sar cati trebuia initial fara cei din stanga deja sariti
		CautaCopil(aux+1,(left+right)/2+1,right,val-heap[aux]);
	else
		CautaCopil(aux,left,(left+right)/2,val);
}

int main(int argc, char* argv[])
{
	int N,i,Nr,val;
	FILE *fpr,*fpw;
	fpr = fopen("order.in","r");
	fpw = fopen("order.out","w");
	fscanf(fpr,"%d",&N);

	ConstruiesteHeap(1,1,N);

	fprintf(fpw,"2");
	nrC = 0;
	AdaugaEliminare(1,1,N,2);
	retC = 1;
	Nr = N-1;
	for(i=2;i<=N;i++){
		val = (nrC+i-1)%Nr+1;
		CautaCopil(1,1,N,val);
		nrC = 0;
		AdaugaEliminare(1,1,N,retC);
		fprintf(fpw," %d",retC);
		Nr--;
	}

	fclose(fpr);
	fclose(fpw);
	return 0;
}