Cod sursa(job #438852)

Utilizator dragos.denaDena Dragos dragos.dena Data 11 aprilie 2010 01:36:11
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 5.92 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stdint.h>
#include <stdlib.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
uint32_t max_sorted;

ifstream in ("gutui.in");
ofstream out ("gutui.out");

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

	public:
		Level(uint32_t _id);		
		void add_gut(uint32_t g);	// O(1)
		void partial_sort_();		// O(data.size() * log(max_sorted - id))
		uint32_t max();				// O(1)
		uint32_t get_max();			// O(1)
		uint32_t get_id();			// O(1)
		uint32_t get_size();		// O(1)
};

class LevelStructure {
	private:
		vector<Level> levels;
		uint32_t* index;
		uint32_t current_level;
		uint32_t size;
		uint32_t capacity;

	public:
		LevelStructure(uint32_t _capacity);							
		void add_gut_to_level(uint32_t gut, uint32_t level_index);	// O(1)
		void iteration_reset();										// O(1)
		Level* get_next();											// O(1)
		void prepare_for_iteration();								// O(size * log(size))
		vector<Level> get_levels_vector();							// O(1)
		uint32_t get_size();										// O(1)
};

class LevelHeap {

	private:
		uint32_t size;
		vector<Level> data;
		uint32_t elements;
		uint32_t capacity;
		void bring_up(uint32_t index);		// O(log(size))
		void bring_down(uint32_t index);	// O(log(size))

	public:
		LevelHeap(vector<Level> level_data, uint32_t _capacity);
		uint32_t add_level();		// O(log(size))
		uint32_t get_max();			// O(log(size))
		uint32_t elements_number();	// O(1)
		uint32_t next_index();		// O(1)
		void debug();				// O(1)
};

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

int main()
{
	// Notam m = min(LEVELS,N)
	in >> N >> H >> U;
	max_sorted = (LEVELS < N) ? LEVELS:N;
	uint32_t sum = 0;
	uint32_t temp_g, temp_h;
	LevelStructure levels (LEVELS);
	 
	for(uint32_t i = 0; i < N; i ++)	// O(n)
	{
		in >> temp_h >> temp_g;
		levels.add_gut_to_level(temp_g, INDEX(temp_h));
	}
	
	levels.prepare_for_iteration();		// O(m*lgm)
	
	levels.iteration_reset();
	for(Level* crt_level = levels.get_next(); crt_level != NULL; crt_level = levels.get_next ())	// O(n * lgm)
		(*crt_level).partial_sort_();

	LevelHeap level_heap(levels.get_levels_vector(), levels.get_size());	// O(1)


	uint32_t current;
	for(uint32_t i = 0; i < levels.get_size(); i ++)	// O(m lgm)
	{
		current = level_heap.add_level();
		uint32_t next_index = level_heap.next_index();
		if(next_index == 0) next_index = LEVELS;
		for(uint32_t i = current; i < next_index && level_heap.elements_number() != 0; i ++)
		{
			sum += level_heap.get_max();
		}
	}
	
	out << sum;

	return 0;
}

Level::Level(uint32_t _id)
{
	id = _id;
	crt_max = 0;
}

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

void Level::partial_sort_()
{
//	cout << max_sorted << " " << id << " " << data.size() << endl;
	uint32_t n = max_sorted - id;
	partial_sort(data.begin(), data.begin() + ((n < data.size()) ? n:data.size()), data.end(), compare_g);
}

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];
}

uint32_t Level::get_id()
{
	return id;
}
uint32_t Level::get_size()
{
	return data.size() - crt_max;
}

LevelHeap::LevelHeap(vector<Level> level_data, uint32_t _capacity)
{
	data = level_data;
	size = 0;
	capacity = _capacity;
	elements = 0;
}

uint32_t LevelHeap::add_level()
{
	size ++;
	uint32_t ret = data[size - 1].get_id();
	elements += data[size - 1].get_size();
	bring_up(size - 1);
	return ret;
}

uint32_t LevelHeap::get_max()
{
	uint32_t max = data[0].get_max();
	bring_down(0);
	elements --;
	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);	
	}
}

uint32_t LevelHeap::elements_number()
{
	return elements;
}

uint32_t LevelHeap::next_index()
{
	if(size == capacity)
		return 0;
	return data[size].get_id();
}


void LevelStructure::add_gut_to_level(uint32_t gut, uint32_t level_index)
{
	if(index[level_index] == 0)
	{
		//cout << "aici" << endl;
		Level new_level (level_index);
		new_level.add_gut(gut);
		levels.push_back(new_level);
		index[level_index] = levels.size();
	}
	else
	{
		//cout << "aici2" << endl;
		levels[index[level_index] - 1].add_gut(gut);
	}
	//cout << level_index << " " << index[level_index] << endl;
}

LevelStructure::LevelStructure(uint32_t _capacity)
{
	capacity = _capacity;
	index = (uint32_t*)calloc(capacity, sizeof(uint32_t));
}

void LevelStructure::iteration_reset()
{
	current_level = 0;
}

Level* LevelStructure::get_next()
{
	current_level ++;
	if(current_level - 1 < levels.size())
		return &levels[current_level - 1];
	return NULL;
}

void LevelStructure::prepare_for_iteration()
{
	sort(levels.begin(), levels.end(), compare_lvl_by_id);
}

vector<Level> LevelStructure::get_levels_vector()
{
	return levels;
}

uint32_t LevelStructure::get_size()
{
	return levels.size();
}