Cod sursa(job #463569)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 16 iunie 2010 14:08:45
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.96 kb
#include <stdio.h>
#include <stdlib.h>

#define file_in "gutui.in"
#define file_out "gutui.out"

#define N_MAX 100000

typedef unsigned long long int ULLI;

ULLI sum_w; // suma ceruta 

struct s_gutuie {
	
	int h, w; // inaltime si greutate
};

typedef struct s_gutuie* gutuie;

gutuie G[N_MAX];
int n, h_max , u, dim_v;
char *V; // descris mai jos

struct s_cell {
	
	int f_z; // first zero
	int sons; // numarul de fii
	struct s_cell * up; 
};

typedef struct s_cell* cell;

cell* C; // descris mai jos

cell new_cell ( void ) { // returneaza o celula vida 
	
	cell new_c = (cell) calloc ( 1 , sizeof ( struct s_cell ) );

	return new_c;
}

void init ( void ) { // aloca memorie pentru gutui

	int i;
	for(i=0;i<n;++i)
		G[i] = (gutuie) calloc ( 1 , sizeof ( struct s_gutuie ) );
}

void read_input ( void ) { 
	
	int i;
	FILE* fin = fopen ( file_in , "r" );
	fscanf(fin , "%d %d %d", &n , &h_max , &u);
	init ();
	for(i=0;i<n;++i) 
		fscanf(fin , "%d %d", &(G[i]->h) , &(G[i]->w) );
	fclose(fin);
}
void concat ( int a, int m, int b ) {  // concateneaza doua siruri ordonate
	
	gutuie* G_aux = (gutuie*) calloc ( b-a+1 , sizeof(gutuie) );
	int i, j, k;
	i = a; j = m+1; k = 0;

	while ( i<=m && j<= b ) 
		if ( G[i] -> w > G[j] -> w ) G_aux[k++] = G[i++];
		else G_aux[k++] = G[j++];
	
	while ( i<=m ) G_aux[k++] = G[i++];
	while ( j<=b ) G_aux[k++] = G[j++];
	
	for(i=a, k=0;i<=b;++i)
		G[i] = G_aux [k++];

	free ( G_aux );
}

void merge_sort ( int a, int b ) {
	

	if ( a < b ){
		
		int m = (a+b)/2;
		merge_sort(a,m);
		merge_sort(m+1,b);
		concat(a,m,b);
	}
}

int to_seg ( int i ) { // determina segmentul ( nivelul ) aferent unei gutui ( inaltimii acestetia )
	
	return (h_max - G[i]->h ) / u;
}

cell get_cell ( int loc ) { 
	
	cell c = C[loc];
	for( ; c -> up ; c = c -> up );
	
	return c;
}

int get_f_z ( int loc ) { 
	
	return get_cell ( loc ) -> f_z;
}

void connect_cells ( int l1 , int l2 ) {
	
	int s1, s2;
	cell c1 = get_cell ( l1 ) ;
	cell c2 = get_cell ( l2 ) ;
	
	s1 = c1 -> sons;
	s2 = c2 -> sons;
	
	if ( s1 < s2 ) {
		
		c1 -> up = c2;
		c2 -> f_z = c1 -> f_z;
		c2 -> sons += c1 -> sons;
	}
		
	if ( s1 > s2 ) {
		
		c2 -> up = c1;
		c1 -> sons += c2 -> sons;
	}
	
	if ( s1 == s2 ) {
		
		cell c = new_cell ();
		c -> f_z = c1 -> f_z;
		c -> up = NULL;
		c -> sons = s1 + s2;
		c1 -> up = c;
		c2 -> up = c;
	}
}

void put_one ( int loc ) {
	
	int st, dr;
	st = (loc >0 && V[loc-1] == 1);
	dr = (loc<dim_v-1 && V[loc+1] == 1 );
	
		
	V[loc] = 1;
	if ( st && !dr)  {
			
		C[loc] = C[loc-1];
		cell c;
		c = get_cell ( loc );
		c -> sons ++;
	}
		
	if ( !st && dr) {
		 
		C[loc] = C[loc+1];
		cell c = get_cell (loc);
		c -> f_z = loc-1;
		c -> sons ++;
	}
			
	if ( !st && !dr) {
		
		C[loc] = new_cell ();
		C[loc] -> f_z = loc-1;
		C[loc] -> up = NULL;
		C[loc] -> sons = 1;
	}
		
	if ( st && dr ) {
			
		C[loc] = C [loc - 1];
		connect_cells ( loc, loc+1 );
	}	
}
	

int search_V ( int loc ) {
	
	if ( V[loc] == 0 ) {
		
		put_one ( loc );
		return loc;
	}
	
	if ( V[loc] == 1 ) {
		
		int first_z = get_f_z ( loc );
		if ( first_z < 0 ) return first_z;
		put_one ( first_z );	
		return first_z;
	}	
	
	return 0;		
}

void calculate ( void ) {
	
	merge_sort (0,n-1);
	
	int i;
	
	int nr_seg = h_max / u + ( (h_max%u) ? 1 : 0 );
	dim_v = nr_seg;
	
	/* Problema se reduce la urmatoarea:
	 * Avand vectorul V de lungime nr_seg, se fac N operatii de tipul
	 * search_V ( ind ) <=> 1.care este primul 0 la un indice mai mic sau egal cu ind +
	 * 2. pune 1 acolo daca a gasit o locatie in interiorul lui V ( cu indice >= 0)
	 * Mai multe detalii in README
	 */
	
	V = (char *) calloc ( nr_seg , sizeof( char ) );
	C = (cell *) calloc ( nr_seg , sizeof( cell ) );
	
	for(i=0;i<n;++i)
		if(search_V ( to_seg (i) ) >= 0 ) sum_w+=G[i]->w;
		
	free ( V );
}	

void print_rez ( void ) {
	
	FILE * fout = fopen ( file_out , "w");
	fprintf(fout, "%llu\n" , sum_w);
	fclose(fout);
}	

void end ( void ) {
	
	int i;
	for(i=0;i<n;++i)
		free ( G[i] ); 
}

int main ( void ) {
	
	read_input ();
	calculate ();
	print_rez();

	return 0;
}