Pagini recente » Cod sursa (job #172197) | Cod sursa (job #324883) | Cod sursa (job #334898) | Cod sursa (job #1034886) | Cod sursa (job #438818)
Cod sursa(job #438818)
#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);
void partial_sort_();
uint32_t max();
uint32_t get_max();
uint32_t get_id();
uint32_t get_size();
void debug();
};
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);
void iteration_reset();
Level* get_next();
void prepare_for_iteration();
vector<Level> get_levels_vector();
uint32_t get_size();
void debug();
};
class LevelHeap {
private:
uint32_t size;
vector<Level> data;
uint32_t elements;
uint32_t capacity;
void bring_up(uint32_t index);
void bring_down(uint32_t index);
public:
LevelHeap(vector<Level> level_data, uint32_t _capacity);
uint32_t add_level();
uint32_t get_max();
uint32_t elements_number();
uint32_t current_index();
uint32_t next_index();
void debug();
};
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()
{
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(m * lgm)
(*crt_level).partial_sort_();
LevelHeap level_heap(levels.get_levels_vector(), levels.get_size());
uint32_t current;
for(uint32_t i = 0; i < levels.get_size(); i ++)
{
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();
}
}/*
while(current != LEVELS && level_heap.elements_number() != 0)
{
sum += level_heap.get_max();
current ++;
}*/
out << sum;
/*
//Level* levels = new Level[LEVELS];
//Level
for(uint32_t i = 0; i < N; i ++)
{
in >> temp_h >> temp_g;
levels[INDEX(temp_h)].add_gut(temp_g, INDEX(temp_h));
if (levels[INDEX(temp_h)].)
}
for(uint32_t i = 0; i < LEVELS; i ++)
levels[i].partial_sort_(max_sorted - i);
LevelHeap level_heap(levels);
for(uint32_t k = 0; k < LEVELS; k ++)
{
level_heap.add_level();
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();
}
void Level::debug()
{
cout << "----------" << endl;
cout << "Level " << get_id() << endl;
for(uint32_t i = crt_max; i < data.size(); i ++)
{
cout << "(" << i << "," << data[i] << ")" << endl;
}
}
void LevelStructure::debug()
{
for(uint32_t i = 0; i < levels.size(); i ++)
{
levels[i].debug();
}
}
void LevelHeap::debug()
{
cout << "########" << endl;
cout << "Heap size: " << size << endl;
for(uint32_t i = 0; i < size; i ++)
data[i].debug();
}