Cod sursa(job #438192)

Utilizator dragos.denaDena Dragos dragos.dena Data 10 aprilie 2010 15:52:13
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.95 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stdint.h>

#define INDEX(h)  (((H)/(U)) - ((H - (h))/U)) 		// nivelul in care intra o anumita gutaie in functie de inaltime
#define LEVELS    ((H/U) + 1)						// numarul de nivele in functie de inaltimea maxima si diferenta dintre 
													// nivele
// Macrouri pentru heap-uri
#define PARENT(id) 	((id + 1)/2 - 1)
#define LEFT(id) 	((id)*2 + 1)
#define RIGHT(id)	((id)*2 + 2)

using namespace std;
uint32_t N, H, U;		// Numarul de Gutui, Inaltimea maxima, Pasul de inaltare
ifstream in ("gutui.in");
ofstream out ("gutui.out");

typedef struct _iter_info
{
	uint32_t max;
	uint32_t index;
} IterInfo, *PIterInfo;

class Level {
	private:
		//vector<uint32_t> data;
		//uint32_t crt_max;

	public:
		uint32_t crt_max;
		vector<uint32_t> data;
		void add_gut(uint32_t g);
		void partial_sort_(uint32_t n);
		uint32_t max();
		uint32_t get_max();
};

class LevelHeap {
	private:
		
		void bring_up(uint32_t index);
		void bring_down(uint32_t index);

	public:
		uint32_t size;
		Level* data;
		LevelHeap(Level* level_data);
		void add_level();
		uint32_t get_max();
};

bool compare_g(uint32_t g1, uint32_t g2) { return (g1 > g2); }
bool compare_lvl(Level l1, Level l2) { return (l1.max() < l2.max()); }

int main()
{
	in >> N >> H >> U;
	uint32_t max_sorted = (LEVELS < N) ? LEVELS:N;
	uint32_t sum = 0;
	uint32_t temp_g, temp_h;
	Level* levels = new Level[LEVELS];
	for(uint32_t i = 0; i < N; i ++)
	{
		in >> temp_h >> temp_g;
		levels[INDEX(temp_h)].add_gut(temp_g);
	}
	

	for(uint32_t i = 0; i < LEVELS; i ++)
		levels[i].partial_sort_(max_sorted - i);
/*
	for(uint32_t i = 0; i < LEVELS; i ++)
		{
			out << "-------------" << endl << "Level " << i << endl;
			for(uint32_t j = 0; j < levels[i].data.size(); j ++)
			{
				out << levels[i].data[j] << " ";
			}
			out << endl;
		}
*/	
	 LevelHeap level_heap(levels);

	for(uint32_t k = 0; k < LEVELS; k ++)
	{	
		level_heap.add_level();
		/*out << "#########" << endl << "Heap size " << level_heap.size << endl;
		for(uint32_t i = 0; i < level_heap.size; i ++)
		{
			out << "---------" << endl << "Level " << i << endl;
			for(uint32_t j = level_heap.data[i].crt_max; j < level_heap.data[i].data.size(); j ++)
				out << level_heap.data[i].data[j] << " ";
			out << endl;
		}*/
		sum += level_heap.get_max();

		/*out << "#########" << endl << "Heap size " << level_heap.size << endl;
		for(uint32_t i = 0; i < level_heap.size; i ++)
		{
			out << "---------" << endl << "Level " << i << endl;
			for(uint32_t j = level_heap.data[i].crt_max; j < level_heap.data[i].data.size(); j ++)
				out << level_heap.data[i].data[j] << " ";
			out << endl;
		}*/
	}

	out << sum;
	return 0;
}

void Level::add_gut(uint32_t g)
{
	data.push_back(g);
}

void Level::partial_sort_(uint32_t n)
{
	partial_sort(data.begin(), data.begin() + ((n < data.size()) ? n:data.size()), data.end(), compare_g);
	crt_max = 0;
}

uint32_t Level::max()
{
	if(data.size() <= crt_max)
		return 0;
	return data[crt_max];
}

uint32_t Level::get_max()
{
	if(data.size() <= crt_max)
		return 0;
	crt_max ++;
	return data[crt_max - 1];
}

LevelHeap::LevelHeap(Level* level_data)
{
	data = level_data;
	size = 0;
}

void LevelHeap::add_level()
{
	size ++;
	bring_up(size - 1);
}

uint32_t LevelHeap::get_max()
{
	uint32_t max = data[0].get_max();
	bring_down(0);
	return max;
}

void LevelHeap::bring_up(uint32_t index)
{
	if(index <= 0)
		return;
	if(data[index].max() > data[PARENT(index)].max() )
	{
		Level temp = data[index];
		data[index] = data[PARENT(index)];
		data[PARENT(index)] = temp;
		bring_up(PARENT(index)); 
	}
}

void LevelHeap::bring_down(uint32_t index)
{
	uint32_t max;
	uint32_t left = LEFT(index), right = RIGHT(index);
	if(left < size && data[left].max() > data[index].max())
		max = left;
	else
		max = index;
	if(right < size && data[right].max() > data[max].max())
		max = right;
	if(max != index)
	{
		Level temp = data[max];
		data[max] = data[index];
		data[index] = temp;
		bring_down(max);	
	}
}