vadimk772336

Untitled

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