vadimk772336

Untitled

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