Количество ячеек 1<=N<=2^(31)-1, количество запросов 1<=m<=10^5. На вход подаются числа N и M, а затем M чисел, если число положительное - выделение памяти, отрицательное - освобождение. Для каждого запроса на выделение памяти в выход выводится одно число на отдельной строке с результатом выполнения запроса. Если память была выделена, выводится номер первой ячейки памяти в выделенном блоке, иначе выводится -1.
Для хранения свободных отрезков используется куча с итераторами на отрезки из двусвязного списка, в котором хранятся все отрезки. Приведенное решение имеет асимптотику O(m log(m)).
#include <vector>
#include <list>
#include <algorithm>
#include <cstdio>
using std::vector;
using std::list;
using std::swap;
struct Chunk {
int start_;
int length_;
bool is_free_;
int index_;
Chunk(int start = 0, int length = 0, bool is_free = false, int index = 0):
start_(start), length_(length), is_free_(is_free), index_(index) {}
bool operator <(const Chunk& other) const {
if (length_ < other.length_) {
return true;
}
if (length_ == other.length_) {
return start_ > other.start_;
}
return false;
}
bool operator ==(const Chunk& other) const {
return start_ == other.start_ && length_ == other.length_ &&
is_free_ == other.is_free_ && index_ == other.index_;
}
bool operator >(const Chunk& other) const {
return other < *this;
}
};
class MaxChunkHeap {
private:
vector<list<Chunk>::iterator> array;
public:
bool empty() const {
return array.empty();
}
void Heapify(int root_index) {
int left_son_index, right_son_index, largest_index;
left_son_index = 2 * root_index + 1;
right_son_index = 2 * root_index + 2;
largest_index = root_index;
if (left_son_index < array.size() &&
*(array[left_son_index]) > *(array[largest_index])) {
largest_index = left_son_index;
}
if (right_son_index < array.size() &&
*(array[right_son_index]) > *(array[largest_index])) {
largest_index = right_son_index;
}
if (largest_index != root_index) {
swap(array[root_index]->index_, array[largest_index]->index_);
swap(array[root_index], array[largest_index]);
Heapify(largest_index);
}
}
void ChangeKey(int index, list<Chunk>::iterator new_key) {
array[index] = new_key;
new_key->index_ = index;
Heapify(index);
while (index > 0 && *(array[(index - 1) / 2]) < *(array[index])) {
swap(array[(index - 1) / 2]->index_, array[index]->index_);
swap(array[(index - 1) / 2], array[index]);
index = (index - 1) / 2;
}
}
void Insert(list<Chunk>::iterator new_key) {
array.push_back(new_key);
ChangeKey(array.size() - 1, new_key);
}
list<Chunk>::iterator GetMax() {
return array[0];
}
list<Chunk>::iterator ExtractMax() {
list<Chunk>::iterator max_element = array[0];
array[0] = array[array.size() - 1];
array[0]->index_ = 0;
array.pop_back();
Heapify(0);
return max_element;
}
void Remove(int index) {
if (array.empty())
return;
array[index] = array[array.size() - 1];
array[index]->index_ = index;
array.pop_back();
ChangeKey(index, array[index]);
}
MaxChunkHeap() {}
};
class Allocator {
private:
MaxChunkHeap memory_heap_;
list<Chunk> chunks_list_;
vector<list<Chunk>::iterator> allocated_chunks_;
int operations_counter_;
public:
Allocator(int size_of_memory) {
chunks_list_.push_back(Chunk(1, size_of_memory , true, 0));
memory_heap_.Insert(chunks_list_.begin());
operations_counter_ = 0;
}
int allocateMemory(int size) {
++operations_counter_;
allocated_chunks_.resize(operations_counter_, chunks_list_.end());
if (memory_heap_.empty()) {
return -1;
}
if (memory_heap_.GetMax()->length_ < size) {
return -1;
}
list<Chunk>::iterator free_chunk = memory_heap_.ExtractMax();
Chunk new_chunk(free_chunk->start_, size, false);
allocated_chunks_[operations_counter_ - 1] =
chunks_list_.insert(free_chunk, new_chunk);
if (free_chunk->length_ == size) {
chunks_list_.erase(free_chunk);
return allocated_chunks_[operations_counter_ - 1]->start_;
}
free_chunk->length_ -= size;
free_chunk->start_ += size;
memory_heap_.Insert(free_chunk);
return allocated_chunks_[operations_counter_ - 1]->start_;
}
void deallocateMemory(int num) {
++operations_counter_;
if (allocated_chunks_[num - 1] == chunks_list_.end()) {
return;
}
allocated_chunks_[num - 1]->is_free_ = true;
// Merge with prev
if (allocated_chunks_[num - 1] != chunks_list_.begin()) {
list<Chunk>::iterator prev_chunk = allocated_chunks_[num - 1];
--prev_chunk;
if (prev_chunk->is_free_) {
allocated_chunks_[num - 1]->length_ += prev_chunk->length_;
allocated_chunks_[num - 1]->start_ = prev_chunk->start_;
memory_heap_.Remove(prev_chunk->index_);
chunks_list_.erase(prev_chunk);
}
}
// Merge with next
if (allocated_chunks_[num - 1] != --(chunks_list_.end())) {
list<Chunk>::iterator next_chunk = allocated_chunks_[num - 1];
++next_chunk;
if (next_chunk->is_free_) {
allocated_chunks_[num - 1]->length_ += next_chunk->length_;
memory_heap_.Remove(next_chunk->index_);
chunks_list_.erase(next_chunk);
}
}
memory_heap_.Insert(allocated_chunks_[num - 1]);
}
};
void readInputToVector(vector<int> *vec) {
int number_of_numbers, cur_number;
scanf("%d", &number_of_numbers);
for (int i = 0; i < number_of_numbers; ++i) {
scanf("%d", &cur_number);
vec->push_back(cur_number);
}
}
void performRequests(const vector<int> &requests, vector<int> *output_vec,
Allocator *allocator) {
for (vector<int>::const_iterator it = requests.begin(); it != requests.end();
++it) {
if (*it > 0) {
output_vec->push_back(allocator->allocateMemory(*it));
}
if (*it < 0) {
allocator->deallocateMemory(-(*it));
}
}
}
void writeOutput(const vector<int> &vec) {
for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
printf("%d\n", *it);
}
}
int main() {
int size_of_memory;
scanf("%d", &size_of_memory);
Allocator allocator(size_of_memory);
vector<int> requests;
readInputToVector(&requests);
vector<int> output_vec;
performRequests(requests, &output_vec, &allocator);
writeOutput(output_vec);
return 0;
}