Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct heap_elements;
- struct list_segments
- {
- int l;
- int r;
- int status;
- struct list_segments* next;
- struct list_segments* prev;
- //int req_num;
- int to_heap;
- };
- struct heap_elements
- {
- int l;
- int r;
- int position;
- list_segments* to_list;
- };
- bool operator<(const heap_elements& a, const heap_elements& b)
- {
- if ((a.r - a.l < b.r - b.l))
- return true;
- if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
- return true;
- return false;
- }
- class Heap
- {
- static const int SIZE = 100;
- struct heap_elements* h;
- int HeapSize;
- public:
- Heap();
- void siftup();
- void siftdown(int);
- void add(heap_elements);
- void delete_vertex(int);
- bool isempty();
- heap_elements* get_head();
- void out();
- };
- Heap::Heap()
- {
- h = new heap_elements[SIZE];
- HeapSize = 0;
- }
- heap_elements* Heap::get_head()
- {
- return &h[0];
- }
- bool Heap::isempty()
- {
- if (HeapSize == 0)
- return true;
- return false;
- }
- void Heap::siftup()
- {
- int curr, parent;
- curr = HeapSize - 1;
- parent = (curr - 1) / 2;
- while (parent >= 0 && curr > 0)
- {
- if (h[parent] < h[curr])
- {
- heap_elements buff = h[curr];
- h[curr] = h[parent];
- h[parent] = buff;
- h[curr].position = curr;
- h[parent].position = parent;
- h[curr].to_list->to_heap = curr;
- h[parent].to_list->to_heap = parent;
- }
- curr = parent;
- parent = (curr - 1) / 2;
- }
- }
- void Heap::siftdown(int position)
- {
- int parent, max_child;
- int curr = position;
- int child_l = 2 * curr + 1;
- int child_r = 2 * curr + 2;
- if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- while (child_l < HeapSize)
- {
- if (child_l == HeapSize - 1)
- max_child = child_l;
- else if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- if (h[curr] < h[max_child])
- {
- heap_elements buff = h[curr];
- h[curr] = h[max_child];
- h[max_child] = buff;
- h[curr].position = curr;
- h[max_child].position = max_child;
- h[curr].to_list->to_heap = curr;
- h[max_child].to_list->to_heap = max_child;
- }
- curr = max_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- }
- void Heap::add(heap_elements vertex)
- {
- h[HeapSize] = vertex;
- h[HeapSize].position = HeapSize;
- if (h[HeapSize].to_list != NULL)
- h[HeapSize].to_list->to_heap = HeapSize;
- HeapSize++;
- siftup();
- }
- void Heap::delete_vertex(int position)
- {
- h[position] = h[HeapSize - 1];
- h[HeapSize - 1].l = 0;
- h[HeapSize - 1].r = 0;
- HeapSize--;
- siftdown(position);
- }
- void Heap::out(void)
- {
- for (int i = 0; i < HeapSize; i++)
- {
- cout << "(" << h[i].l << "," << h[i].r << ") ";
- }
- cout << endl;
- }
- //----------------------------------------------------------------LIST SEGMENTS BEGIN
- class LIST_SEGMENTS
- {
- struct list_segments* Head;
- int Count;
- public:
- LIST_SEGMENTS();
- list_segments* get_head();
- void add(int, int, int, int, list_segments*);
- void delete_segment(list_segments*);
- void add_head(int, int, int, int);
- void Print();
- };
- LIST_SEGMENTS::LIST_SEGMENTS()
- {
- Head = NULL;
- Count = 0;
- }
- void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
- {
- list_segments* buff = new list_segments;
- buff->prev = 0;
- buff->l = l;
- buff->r = r;
- buff->status = status;
- buff->next = Head;
- if (Head != NULL)
- Head->prev = buff;
- Head = buff;
- Count++;
- }
- void LIST_SEGMENTS::add(int l, int r, int status, int to_heap, list_segments* segment)
- {
- list_segments* after_segment = new list_segments;
- after_segment->l = l;
- after_segment->r = r;
- after_segment->status = status;
- after_segment->next = segment->next;
- after_segment->prev = segment;
- after_segment->to_heap = to_heap;
- if (segment->next != NULL)
- segment->next->prev = after_segment;
- segment->next = after_segment;
- Count++;
- }
- void LIST_SEGMENTS::delete_segment(list_segments* segment)
- {
- if (segment->next != NULL)
- segment->next->prev = segment->prev;
- if (segment->prev != NULL)
- segment->prev->next = segment->next;
- else
- Head = segment->next;
- delete segment;
- }
- void LIST_SEGMENTS::Print()
- {
- list_segments* buff = Head;
- while (buff->next != NULL)
- {
- cout << "(" << buff->l << ";" << buff->status << ";" << buff->r << ")"
- << ";";
- buff = buff->next;
- }
- cout << "(" << buff->l << ";" << buff->status << ";" << buff->r << ")"
- << ";\n";
- }
- list_segments* LIST_SEGMENTS::get_head()
- {
- return Head;
- }
- int main()
- {
- int N1, N2, N3, N4, N5;
- int M1, M2, M3, M4, M5;
- //отказ -1
- //освободили -2
- //нечего освобождать -3
- N1 = 6;
- M1 = 8;
- int req_mas1[] = { 2, 3, -1, 3, 3, -5, 2, 2 };
- int true_answer_mas1[] = { 1, 3, -2, -1, -1, -3, 1, -1 };
- N2 = 1;
- M2 = 7;
- int req_mas2[] = { 2, 2, 1, 1, -4, -1, -3 }; // answer = -1 -1 1 -1 none none free
- int true_answer_mas2[] = { -1, -1, 1, -1, -3, -3, -2 };
- N3 = 6;
- M3 = 9;
- int req_mas3[] = { 2, 2, 2, -1, -3, -2, 2 ,2,2}; //Тест со слиянием answer 1 3 5 free free free
- int true_answer_mas3[] = { 1, 3, 5, -2, -2, -2, 1,3,5 };
- N4 = 6;
- M4 = 2;
- int req_mas4[] = { 3, -1}; //Тест со слиянием answer 1 3 5 free free free
- int true_answer_mas4[] = { 1,-2};
- /*
- N5 = 6; M5 = 8;
- int req_mas5[] = {2,3,-1,3,3,-5,2,2};
- */
- Heap heap;
- int N, M, K;
- //Записываю данные для
- //теста################################################################################
- int number_test = 3;
- if (number_test == 1) {
- N = N1;
- M = M1;
- }
- if (number_test == 2) {
- N = N2;
- M = M2;
- }
- if (number_test == 3) {
- N = N3;
- M = M3;
- }
- if (number_test == 4) {
- N = N4;
- M = M4;
- }
- int req[M];
- int answer_mas[M];
- int true_answer_mas[M];
- for (int j = 0; j < M; ++j)
- {
- if (number_test == 4) {
- req[j] = req_mas4[j];
- answer_mas[j] = -1;
- true_answer_mas[j] = true_answer_mas4[j];
- }
- if (number_test == 3) {
- req[j] = req_mas3[j];
- answer_mas[j] = -1;
- true_answer_mas[j] = true_answer_mas3[j];
- }
- if (number_test == 2) {
- req[j] = req_mas2[j];
- answer_mas[j] = -1;
- true_answer_mas[j] = true_answer_mas2[j];
- }
- if (number_test == 1) {
- req[j] = req_mas1[j];
- answer_mas[j] = -1;
- true_answer_mas[j] = true_answer_mas1[j];
- }
- }
- //Записываю данные для теста--------------------------
- cout << "N,M = " << N << " " << M << endl;
- // cout << "Enter N: ";
- // cin >> N;
- heap_elements vertex;
- vertex.l = 1;
- vertex.r = N;
- vertex.to_list = NULL;
- vertex.position = 0;
- LIST_SEGMENTS List;
- List.add_head(1, N, 1, 0);
- vertex.to_list = List.get_head();
- heap.add(vertex);
- list_segments segment;
- heap_elements* heap_head;
- // cout << "Enter M: ";
- // cin >> M;
- list_segments* requests[M];
- for (int i = 0; i < M; ++i)
- {
- K = req[i];
- cout << "\n ЗАПРОС НОМЕР " << i << " Enter K: " << K << endl;
- // cin >> K;
- if (K > 0)
- {
- heap_head = heap.get_head();
- if (!heap.isempty() & (heap_head->r - heap_head->l + 1) >= K)
- {
- if ((heap_head->r - heap_head->l + 1) == K)
- {
- heap_head->to_list->status = 0;
- requests[i] = heap_head->to_list;
- //requests[i]->req_num = i;
- cout << "ANSWER:" << heap_head->l << endl;
- answer_mas[i] = heap_head->l;
- heap.delete_vertex(0);
- }
- else
- {
- // cout << "Можем откусить \n" << endl;
- int old_l = heap_head->l;
- heap_head->l = old_l + K;
- // cout << "Изменившаяся куча после откусывания: " <<heap_head->l<< "\n";
- heap_head->to_list->l = old_l + K;
- if (heap_head->to_list->prev != NULL)
- {
- List.add(old_l, old_l + K - 1, 0, -1, heap_head->to_list->prev);
- requests[i] = heap_head->to_list->prev;
- //requests[i]->req_num = i;
- }
- else
- {
- List.add_head(old_l, old_l + K - 1, 0, -1);
- requests[i] = List.get_head();
- //requests[i]->req_num = i;
- }
- heap.siftdown(0);
- cout << "ANSWER: " << old_l << endl;
- answer_mas[i] = old_l;
- }
- }
- else
- {
- requests[i] = NULL;
- cout << "ANSWER:" << -1 << endl;
- answer_mas[i] = -1;
- }
- }
- else
- {
- int q = abs(K) - 1;
- if (requests[q] != NULL)
- {
- requests[q]->status = 1;
- if (requests[q]->prev != NULL)
- {
- if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
- {
- requests[q]->l = requests[q]->prev->l;
- //requests[requests[q]->prev->req_num] = NULL;
- heap.delete_vertex(requests[q]->prev->to_heap);
- List.delete_segment(requests[q]->prev);
- }
- }
- if (requests[q]->next != NULL)
- {
- if (requests[q]->next->status == 1 & requests[q]->next->l - 1 == requests[q]->r)
- {
- requests[q]->r = requests[q]->next->r;
- //requests[requests[q]->next->req_num] = NULL;
- heap.delete_vertex(requests[q]->next->to_heap);
- List.delete_segment(requests[q]->next);
- }
- }
- vertex.l = requests[q]->l;
- vertex.r = requests[q]->r;
- vertex.to_list = requests[q];
- vertex.position = 0;
- heap.add(vertex);
- requests[i] = requests[q];
- requests[q] = NULL;
- cout << "Освободили, код -2 " << endl;
- answer_mas[i] = -2;
- }
- else
- {
- cout << "Не было занято, поэтому не освободили, код -3 " << endl;
- requests[i] = NULL;
- answer_mas[i] = -3;
- }
- }
- cout << "Куча после запроса: ";
- heap.out();
- cout << "List после запроса: ";
- List.Print();
- cout << "requests после запроса i: ";
- for (int f = 0; f < i + 1; ++f)
- if (requests[f] == NULL)
- cout << " null; ";
- else
- cout << "(" << requests[f]->l << ";" << requests[f]->status << ";" << requests[f]->r
- << ")"
- << "; ";
- cout << "\n---------------";
- }
- cout << "\n answer_mas = ";
- for (int i = 0; i < M; ++i)
- {
- cout << answer_mas[i] << " ";
- }
- cout << endl;
- cout << "true answer_mas = ";
- for (int i = 0; i < M; ++i)
- {
- cout << true_answer_mas[i] << " ";
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment