vadimk772336

Untitled

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