vadimk772336

меньше принтов

Nov 2nd, 2021 (edited)
402
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. enum sort_type
  6. {
  7.     heap_max = 0,
  8.     heap_min = 1
  9. };
  10.  
  11. struct heap_elements
  12. {
  13.     int value;
  14.     int own_ID;
  15. };
  16.  
  17. bool operator<(const heap_elements& a, const heap_elements& b)
  18. {
  19.     return (a.value < b.value);
  20. }
  21.  
  22. class Heap
  23. {
  24.     std::vector<struct heap_elements> h;
  25.     int heap_size;
  26.  
  27. public:
  28.     Heap();
  29.     bool isempty();
  30.     heap_elements get_top();
  31.     void siftup(int sort_type, std::vector<int>& ID_to_Index);
  32.     void siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index);
  33.     void swap(int i, int j, std::vector<int>& ID_to_Index);
  34.     void add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index);
  35.     void delete_vertex(int sort_type,  int ID, std::vector<int>& ID_to_Index);
  36.  
  37. };
  38.  
  39. Heap::Heap()
  40. {
  41.     std::vector<struct heap_elements> h;
  42.     heap_size = 0;
  43. }
  44.  
  45. heap_elements Heap::get_top()
  46. {
  47.     return h[0];
  48. }
  49.  
  50. bool Heap::isempty()
  51. {
  52.     if (heap_size == 0)
  53.         return true;
  54.     return false;
  55. }
  56.  
  57. void Heap::swap(int i, int j, std::vector<int>& ID_to_Index)
  58. {
  59.     heap_elements buff;
  60.     buff = h[i];
  61.     h[i] = h[j];
  62.     h[j] = buff;
  63.  
  64.     ID_to_Index[h[i].own_ID] = i; //На местах в этом массиве лежат айди этой кучи все ок
  65.     ID_to_Index[h[j].own_ID] = j;
  66. }
  67.  
  68. void Heap::siftup(int sort_type, std::vector<int>& ID_to_Index)
  69. {
  70.     int curr = heap_size - 1;
  71.     int parent = (curr - 1) / 2;
  72.     while (curr > 0 & parent >= 0)
  73.     {
  74.         if (sort_type == heap_max & h[parent] < h[curr])
  75.             swap(parent, curr, ID_to_Index);
  76.            
  77.         if (sort_type == heap_min & h[curr] < h[parent])
  78.             swap(parent, curr, ID_to_Index);
  79.  
  80.         curr = parent;
  81.         parent = (curr - 1) / 2;
  82.     }
  83. }
  84.  
  85. void Heap::siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index)
  86. {
  87.  
  88.     int parent, max_child;
  89.  
  90.     int curr = pos;
  91.     int child_l = 2 * curr + 1;
  92.     int child_r = 2 * curr + 2;
  93.  
  94.     //max_child = (h[child_r] < h[child_l]) ? child_l : child_r;
  95.  
  96.     if (h[child_r] < h[child_l])
  97.         max_child = child_l;
  98.     else
  99.         max_child = child_r;
  100.  
  101.     while (child_l < heap_size)
  102.     {
  103.         if (child_l == heap_size - 1)
  104.             max_child = child_l;
  105.         else if (h[child_r] < h[child_l])
  106.             max_child = child_l;
  107.         else
  108.             max_child = child_r;
  109.  
  110.        
  111.         if (sort_type == heap_max & h[curr] < h[max_child])
  112.             swap(curr, max_child, ID_to_Index);
  113.            
  114.         if (sort_type == heap_min & h[max_child] < h[curr])
  115.             swap(curr, max_child, ID_to_Index);
  116.  
  117.         curr = max_child;
  118.         child_l = 2 * curr + 1;
  119.         child_r = 2 * curr + 2;
  120.     }
  121. }
  122.  
  123.  
  124. void Heap::add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index)
  125. {
  126.     heap_elements vertex;
  127.     vertex.value = value;
  128.     vertex.own_ID = ID;
  129.  
  130.     h.push_back(vertex);
  131.    
  132.  
  133.     //Если это новое добавление, то надо делать пушбек,
  134.     //а если старое, то надо просто на место ID написать heap_size
  135.    
  136.     if (ID < ID_to_Index.size()) {
  137.         ID_to_Index[ID] = heap_size;
  138.     }
  139.     else {
  140.         ID_to_Index.push_back(heap_size); //должно быть общее у двух куч
  141.     }
  142.     heap_size++;
  143.     siftup(sort_type, ID_to_Index);
  144. }
  145.  
  146. void Heap::delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index)
  147. {
  148.  
  149.     int pos = ID_to_Index[ID];
  150.    
  151.  
  152.     swap(pos, heap_size - 1, ID_to_Index); //Можно не делать свап
  153.     h.pop_back();
  154.     heap_size--;
  155.     ID_to_Index[ID] = -1; //мб убрать
  156.     siftdown(sort_type, pos, ID_to_Index);
  157. }
  158.  
  159. int main()
  160. {
  161.  
  162.     Heap heap1;
  163.     Heap heap2;
  164.    
  165.     std::vector<int> ID_to_Index;
  166.     int NumberHeap;
  167.     int curr_ID = 0;
  168.     char c;
  169.  
  170.     int N, M, K, ID, ID_root1, root2_ID, ID_root2, count = 1;
  171.     N = 4;
  172.     M = 6;
  173.     K = 1;
  174.     int R = 0, L = 0;
  175.     //int a[N] = { 4, 2, 1, 3, 6, 5, 7 };
  176.     int a[N] = { 1,2,3,4 };
  177.     int ID_to_HeapNumber[N]; //При перебрасывании в другую кучу
  178.    
  179.     heap1.add(heap_max, curr_ID, a[0], ID_to_Index);
  180.     ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  181.     curr_ID++;
  182.  
  183.     for (int i = 0; i < M; ++i)
  184.     {
  185.         cin >> c;
  186.  
  187.         if (c == 'R')
  188.         {
  189.             count++;
  190.             R++;
  191.            
  192.  
  193.             if (count < K)
  194.             {
  195.  
  196.                 heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  197.                 ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  198.                 curr_ID++;
  199.  
  200.                 cout << "--------------------ANSWER--------------: "
  201.                      << "-1" << endl;
  202.  
  203.             }
  204.  
  205.             if (count == K)
  206.             {
  207.  
  208.                 heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  209.                 ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  210.                 curr_ID++;
  211.  
  212.                 cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  213.  
  214.             }
  215.  
  216.             if (count > K)
  217.             {
  218.  
  219.                 if (a[R] > heap1.get_top().value)
  220.                 {
  221.  
  222.                     heap2.add(heap_min, curr_ID, a[R], ID_to_Index);
  223.                     ID_to_HeapNumber[curr_ID] = 2; //Обновляю ID_to_HeapNumber
  224.                     curr_ID++;
  225.  
  226.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  227.  
  228.                    
  229.                 }
  230.  
  231.                 if (a[R] <= heap1.get_top().value)
  232.  
  233.                 {
  234.  
  235.                     heap_elements root1, root2;
  236.  
  237.                     //Запоминаю корень 1 кучи
  238.                     root1 = heap1.get_top();
  239.                     ID_root1 = root1.own_ID;
  240.                    
  241.                     // удаляю корень 1 кучи из 1 кучи
  242.                     heap1.delete_vertex(heap_max, ID_root1, ID_to_Index);
  243.                    
  244.                     // Добавляю корень 1 кучи во 2 кучу не меняя ID
  245.                     heap2.add(heap_min, ID_root1, root1.value, ID_to_Index);
  246.                     ID_to_HeapNumber[ID_root1] = 2; //Обновляю ID_to_HeapNumber
  247.                    
  248.                    
  249.                     //Добавляю в 1 кучу a[R]  меняя айди
  250.                     heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  251.                     ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  252.                     curr_ID++;
  253.                    
  254.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  255.  
  256.                    
  257.                 }
  258.             }
  259.         }
  260.         else
  261.         {
  262.             L++;
  263.             count--;
  264.  
  265.  
  266.  
  267.             ID = L - 1;
  268.             NumberHeap = ID_to_HeapNumber[ID];
  269.            
  270.  
  271.             //Если лежит в куче1 то удаляем там, иначе во 2
  272.             if (NumberHeap == 1)
  273.                 heap1.delete_vertex(heap_max, ID, ID_to_Index);
  274.             else
  275.                 heap2.delete_vertex(heap_min, ID, ID_to_Index);
  276.  
  277.  
  278.             if (count >= K)
  279.             {
  280.                
  281.                
  282.                 //Если удалили из 2 кучи, то первая не пострадала и просто принтим
  283.                 if (NumberHeap == 2)
  284.                 {
  285.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  286.                 }
  287.                
  288.                 else
  289.                 {
  290.                     //Запоминаю вершину кучи2
  291.                     heap_elements root2 = heap2.get_top();
  292.                     root2_ID = root2.own_ID;
  293.                    
  294.                     //Удаляем вершину кучи2, т.к. теперь она в куче1
  295.                     heap2.delete_vertex(heap_min, root2_ID, ID_to_Index);
  296.                    
  297.                     //Добавляем вершину кучи2 в кучу1  не меняя индекс чтобы стало K штук
  298.                     heap1.add(heap_max, root2_ID, root2.value, ID_to_Index);
  299.                     ID_to_HeapNumber[root2_ID] = 1; //Обновляю ID_to_HeapNumber
  300.                    
  301.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  302.                 }
  303.  
  304.             }
  305.             else
  306.             {
  307.                 cout << "--------------------ANSWER--------------: -1 " << endl;
  308.             }
  309.         }
  310.     }
  311.  
  312.     return 0;
  313. }
  314.  
  315.  
Add Comment
Please, Sign In to add comment