Cod sursa(job #544330)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 1 martie 2011 14:00:26
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#define maxN 30005
FILE*f=fopen("schi.in","r");
FILE*g=fopen("schi.out","w");

int A[4 * maxN],i,V[maxN],N,R[maxN],X;

void query(int nod,int st,int dr,int pos){
	if ( st == dr ){
		X = st;
		A[nod] = 0;
		return ;
	}
	int mj = ( st + dr ) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	if ( A[nodst] >= pos )
		query(nodst,st,mj,pos);
	else
		query(noddr,mj+1,dr,pos - A[nodst]);
	
	A[nod] = A[nodst] + A[noddr];
	
}

void init(int nod,int st,int dr){
	if ( st == dr ){
		A[nod] = 1;
		return ;
	}
	int mj = ( dr + st ) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	init(nodst,st,mj);
	init(noddr,mj+1,dr);
	A[nod] = A[nodst] + A[noddr];
	
}

int main () {
	fscanf(f,"%d",&N);
	init(1,1,N);
	
	for ( i = 1 ; i <= N ; ++i ){
		fscanf(f,"%d",&V[i]);
	}
	
	for ( i = N ;  i >= 1 ; --i ){
		query(1,1,N,V[i]);
		R[X] = i;
	}
	
	
	for( i = 1 ; i <= N ; ++i ){
		fprintf(g,"%d\n",R[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}