vadimk772336

Untitled

Oct 28th, 2021
724
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct heap_elements;
  6.  
  7. struct list_segments
  8. {
  9.     int l;
  10.     int r;
  11.     int status;
  12.     struct list_segments* next;
  13.     struct list_segments* prev;
  14.     int req_num;
  15.     int to_heap;
  16. };
  17.  
  18. struct heap_elements
  19. {
  20.     int l;
  21.     int r;
  22.     int position;
  23.     list_segments* to_list;
  24. };
  25.  
  26. bool operator<(const heap_elements& a, const heap_elements& b)
  27. {
  28.  
  29.     if ((a.r - a.l < b.r - b.l))
  30.         return true;
  31.     if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
  32.         return true;
  33.  
  34.     return false;
  35. }
  36.  
  37. class Heap
  38. {
  39.     //static const int SIZE = 100;
  40.     std::vector<struct heap_elements*> h;
  41.     //struct heap_elements* h;
  42.     int HeapSize;
  43.  
  44. public:
  45.     Heap();
  46.     void add(heap_elements);
  47.     void out();
  48.     void siftup();
  49.     void siftdown(int);
  50.     void delete_vertex(int);
  51.     bool isempty();
  52.     heap_elements* get_head();
  53. };
  54.  
  55. Heap::Heap()
  56. {
  57.     std::vector<struct heap_elements*> h = {};
  58.     HeapSize = 0;
  59. }
  60.  
  61. heap_elements* Heap::get_head()
  62. {
  63.     return h[0];
  64. }
  65.  
  66. bool Heap::isempty()
  67. {
  68.     if (HeapSize == 0)
  69.         return true;
  70.     return false;
  71. }
  72.  
  73. void Heap::siftup()
  74. {
  75.     int curr, parent;
  76.     curr = HeapSize - 1;
  77.     parent = (curr - 1) / 2;
  78.     while (parent >= 0 && curr > 0)
  79.     {
  80.         if (h[parent] < h[curr])
  81.         {
  82.             heap_elements* buff = h[curr];
  83.             h[curr] = h[parent];
  84.             h[parent] = buff;
  85.  
  86.             h[curr]->position = curr;
  87.             h[parent]->position = parent;
  88.  
  89.             h[curr]->to_list->to_heap = curr;
  90.             h[parent]->to_list->to_heap = parent;
  91.         }
  92.         curr = parent;
  93.         parent = (curr - 1) / 2;
  94.     }
  95. }
  96.  
  97. void Heap::add(heap_elements vertex)
  98. {
  99.  
  100.     h.push_back(&vertex);
  101.     h[HeapSize]->position = HeapSize;
  102.  
  103.     if (h[HeapSize]->to_list != NULL)
  104.         h[HeapSize]->to_list->to_heap = HeapSize;
  105.  
  106.     HeapSize++;
  107.     siftup();
  108. }
  109.  
  110. void Heap::siftdown(int position)
  111. {
  112.     int parent, max_child;
  113.  
  114.     int curr = position;
  115.     int child_l = 2 * curr + 1;
  116.     int child_r = 2 * curr + 2;
  117.  
  118.     if (h[child_r] < h[child_l])
  119.         max_child = child_l;
  120.     else
  121.         max_child = child_r;
  122.  
  123.     while (child_l < HeapSize)
  124.     {
  125.         if (child_l == HeapSize - 1)
  126.         {
  127.             max_child = child_l;
  128.         }
  129.         else if (h[child_r] < h[child_l])
  130.         {
  131.             max_child = child_l;
  132.         }
  133.         else
  134.         {
  135.             max_child = child_r;
  136.         }
  137.  
  138.         if (h[curr] < h[max_child])
  139.         {
  140.             heap_elements* buff = h[curr];
  141.             h[curr] = h[max_child];
  142.             h[max_child] = buff;
  143.  
  144.             h[curr]->position = curr;
  145.             h[max_child]->position = max_child;
  146.  
  147.             h[curr]->to_list->to_heap = curr;
  148.             h[max_child]->to_list->to_heap = max_child;
  149.         }
  150.  
  151.         curr = max_child;
  152.         child_l = 2 * curr + 1;
  153.         child_r = 2 * curr + 2;
  154.     }
  155. }
  156.  
  157. void Heap::delete_vertex(int position)
  158. {
  159.     h[position] = h[HeapSize - 1];
  160.     h[HeapSize - 1]->l = 0;
  161.     h[HeapSize - 1]->r = 0;
  162.     h.erase(h.begin() + HeapSize - 1);  //Просто написать h.end
  163.     HeapSize--;
  164.     siftdown(position);
  165. }
  166.  
  167. void Heap::out(void)
  168. {
  169.  
  170.     for (int i = 0; i < HeapSize; i++)
  171.     {
  172.         cout << "(" << h[i]->l << "," << h[i]->r << ") ";
  173.     }
  174.     cout << endl;
  175. }
  176.  
  177. //----------------------------------------------------------------LIST SEGMENTS BEGIN
  178. class LIST_SEGMENTS
  179. {
  180.     struct list_segments* Head;
  181.     struct list_segments* element;
  182.     int Count;
  183.  
  184. public:
  185.     LIST_SEGMENTS();
  186.     void add(int, int, int, int, list_segments*);
  187.     void delete_segment(list_segments*);
  188.     void Print();
  189.     void add_head(int, int, int, int);
  190.     list_segments* get_head();
  191. };
  192.  
  193. LIST_SEGMENTS::LIST_SEGMENTS()
  194. {
  195.     Head = NULL;
  196.     Count = 0;
  197. }
  198. void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
  199. {
  200.  
  201.     list_segments* buff = new list_segments;
  202.  
  203.     buff->prev = 0;
  204.     buff->l = l;
  205.     buff->r = r;
  206.     buff->status = status;
  207.     buff->next = Head;
  208.  
  209.     if (Head != NULL)
  210.         Head->prev = buff;
  211.  
  212.     Head = buff;
  213.  
  214.     Count++;
  215. }
  216.  
  217. void LIST_SEGMENTS::add(int l, int r, int status, int to_heap, list_segments* segment)
  218. {
  219.  
  220.     list_segments* after_segment = new list_segments;
  221.  
  222.     after_segment->l = l;
  223.     after_segment->r = r;
  224.     after_segment->status = status;
  225.     after_segment->next = segment->next;
  226.     after_segment->prev = segment;
  227.     after_segment->to_heap = to_heap;
  228.     if (segment->next != NULL)
  229.         segment->next->prev = after_segment;
  230.     segment->next = after_segment;
  231.     Count++;
  232. }
  233.  
  234. void LIST_SEGMENTS::delete_segment(list_segments* segment)
  235. {
  236.     if (segment->next != NULL)
  237.         segment->next->prev = segment->prev;
  238.     if (segment->prev != NULL)
  239.         segment->prev->next = segment->next;
  240.     else
  241.         Head = segment->next;
  242.     delete segment;
  243. }
  244.  
  245. void LIST_SEGMENTS::Print()
  246. {
  247.  
  248.     list_segments* buff = Head;
  249.     while (buff->next != NULL)
  250.     {
  251.         cout << "(" << buff->l << ";" << buff->status << ";" << buff->r << ")"
  252.              << ";";
  253.         buff = buff->next;
  254.     }
  255.  
  256.     cout << "(" << buff->l << ";" << buff->status << ";" << buff->r << ")"
  257.          << ";\n";
  258. }
  259.  
  260. list_segments* LIST_SEGMENTS::get_head()
  261. {
  262.     return Head;
  263. }
  264.  
  265. int main()
  266. {
  267.  
  268.     int N1, N2, N3, N4, N5;
  269.     int M1, M2, M3, M4, M5;
  270.  
  271.     //отказ -1
  272.     //освободили -2
  273.     //нечего освобождать -3
  274.  
  275.     N1 = 6;
  276.     M1 = 8;
  277.     int req_mas1[] = { 2, 3, -1, 3, 3, -5, 2, 2 };
  278.     int true_answer_mas1[] = { 1, 3, -2, -1, -1, -3, 1, -1 };
  279.  
  280.     N2 = 1;
  281.     M2 = 7;
  282.     int req_mas2[] = { 2, 2, 1, 1, -4, -1, -3 }; // answer = -1 -1 1 -1 none none free
  283.     int true_answer_mas2[] = { -1, -1, 1, -1, -3, -3, -2 };
  284.  
  285.     N3 = 6;
  286.     M3 = 9;
  287.     int req_mas3[] = { 2, 2, 2, -1, -3, -2,  2 ,2,2}; //Тест со слиянием answer 1 3 5 free free free
  288.     int true_answer_mas3[] = { 1, 3, 5, -2, -2, -2, 1,3,5 };
  289.  
  290.     /*
  291.     N4 = 6; M4 = 8;
  292.     int req_mas4[] = {2,3,-1,3,3,-5,2,2};
  293.  
  294.     N5 = 6; M5 = 8;
  295.     int req_mas5[] = {2,3,-1,3,3,-5,2,2};
  296.     */
  297.  
  298.     Heap heap;
  299.  
  300.     int N, M, K;
  301.  
  302.     //Записываю данные для
  303.     //теста################################################################################
  304.     N = N1;
  305.     M = M1;
  306.     int req[M];
  307.     int answer_mas[M];
  308.     int true_answer_mas[M];
  309.     for (int j = 0; j < M; ++j)
  310.     {
  311.         req[j] = req_mas1[j];
  312.         answer_mas[j] = -1;
  313.         true_answer_mas[j] = true_answer_mas1[j];
  314.     }
  315.     //Записываю данные для теста--------------------------
  316.  
  317.     cout << "N,M = " << N << " " << M << endl;
  318.     // cout << "Enter N: ";
  319.     // cin >> N;
  320.  
  321.     heap_elements vertex;
  322.     vertex.l = 1;
  323.     vertex.r = N;
  324.     vertex.to_list = NULL;
  325.     vertex.position = 0;
  326.  
  327.     LIST_SEGMENTS List;
  328.     List.add_head(1, N, 1, 0);
  329.  
  330.     vertex.to_list = List.get_head();
  331.     heap.add(vertex);
  332.  
  333.     list_segments segment;
  334.     heap_elements* heap_head;
  335.     // cout << "Enter M: ";
  336.     // cin >> M;
  337.  
  338.     list_segments* requests[M];
  339.     for (int i = 0; i < M; ++i)
  340.     {
  341.  
  342.         K = req[i];
  343.         cout << "\n ЗАПРОС НОМЕР " << i << " Enter K: " << K << endl;
  344.         // cin >> K;
  345.  
  346.         if (K > 0)
  347.         {
  348.  
  349.             heap_head = heap.get_head();
  350.             if (!heap.isempty() & (heap_head->r - heap_head->l + 1) >= K)
  351.             {
  352.                 if ((heap_head->r - heap_head->l + 1) == K)
  353.                 {
  354.                     heap_head->to_list->status = 0;
  355.                     requests[i] = heap_head->to_list;
  356.                     requests[i]->req_num = i;
  357.                     cout << "ANSWER:" << heap_head->l << endl;
  358.                     answer_mas[i] = heap_head->l;
  359.                     heap.delete_vertex(0);
  360.                 }
  361.                 else
  362.                 {
  363.                     // cout << "Можем откусить \n" << endl;
  364.  
  365.                     int old_l = heap_head->l;
  366.                     heap_head->l = old_l + K;
  367.                     // cout << "Изменившаяся куча после откусывания: " <<heap_head->l<< "\n";
  368.  
  369.                     heap_head->to_list->l = old_l + K;
  370.  
  371.                     if (heap_head->to_list->prev != NULL)
  372.                     {
  373.                         List.add(old_l, old_l + K - 1, 0, -1, heap_head->to_list->prev);
  374.                         requests[i] = heap_head->to_list->prev;
  375.                         requests[i]->req_num = i;
  376.                     }
  377.                     else
  378.                     {
  379.                         List.add_head(old_l, old_l + K - 1, 0, -1);
  380.                         requests[i] = List.get_head();
  381.                         requests[i]->req_num = i;
  382.                     }
  383.  
  384.                     heap.siftdown(0);
  385.  
  386.                     cout << "ANSWER: " << old_l << endl;
  387.                     answer_mas[i] = old_l;
  388.                 }
  389.             }
  390.             else
  391.             {
  392.                 requests[i] = NULL;
  393.                 cout << "ANSWER:" << -1 << endl;
  394.                 answer_mas[i] = -1;
  395.             }
  396.         }
  397.  
  398.         else
  399.         {
  400.             int q = abs(K) - 1;
  401.             if (requests[q] != NULL)
  402.             {
  403.  
  404.                 requests[q]->status = 1;
  405.  
  406.                 if (requests[q]->prev != NULL)
  407.                 {
  408.                     if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
  409.                     {
  410.                         requests[q]->l = requests[q]->prev->l;
  411.                         requests[requests[q]->prev->req_num] = NULL;
  412.                         heap.delete_vertex(requests[q]->prev->to_heap);
  413.                         List.delete_segment(requests[q]->prev);
  414.                     }
  415.                 }
  416.                 if (requests[q]->next != NULL)
  417.                 {
  418.                     if (requests[q]->next->status == 1 & requests[q]->next->l - 1 == requests[q]->r)
  419.                     {
  420.                         requests[q]->r = requests[q]->next->r;
  421.                         requests[requests[q]->next->req_num] = NULL;
  422.                         heap.delete_vertex(requests[q]->next->to_heap);
  423.                         List.delete_segment(requests[q]->next);
  424.                     }
  425.                 }
  426.  
  427.                 vertex.l = requests[q]->l;
  428.                 vertex.r = requests[q]->r;
  429.                 vertex.to_list = requests[q];
  430.                 vertex.position = 0;
  431.                 heap.add(vertex);
  432.  
  433.                 requests[i] = requests[q];
  434.                 requests[q] = NULL;
  435.                 cout << "Освободили, код -2 " << endl;
  436.                 answer_mas[i] = -2;
  437.             }
  438.  
  439.             else
  440.             {
  441.                 cout << "Не было занято, поэтому не освободили, код -3 " << endl;
  442.                 requests[i] = NULL;
  443.                 answer_mas[i] = -3;
  444.             }
  445.         }
  446.  
  447.         cout << "Куча после запроса: ";
  448.         heap.out();
  449.         cout << "List после запроса: ";
  450.         List.Print();
  451.         cout << "requests после запроса i: ";
  452.         for (int f = 0; f < i + 1; ++f)
  453.             if (requests[f] == NULL)
  454.                 cout << " null; ";
  455.             else
  456.                 cout << "(" << requests[f]->l << ";" << requests[f]->status << ";" << requests[f]->r
  457.                      << ")"
  458.                      << "; ";
  459.         cout << "\n---------------";
  460.     }
  461.  
  462.     cout << "\n answer_mas      = ";
  463.     for (int i = 0; i < M; ++i)
  464.     {
  465.         cout << answer_mas[i] << " ";
  466.     }
  467.     cout << endl;
  468.  
  469.     cout << "true answer_mas  = ";
  470.     for (int i = 0; i < M; ++i)
  471.     {
  472.         cout << true_answer_mas[i] << " ";
  473.     }
  474.  
  475.     return 0;
  476. }
  477.  
RAW Paste Data