Advertisement
vadimk772336

недописанное ласт задание

Dec 21st, 2021
1,365
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.19 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 dots
  12. {
  13.     int l;
  14.     int r;
  15.     int to_heap;
  16.     int number_heap = 0;
  17. };
  18.  
  19. struct heap_element
  20. {
  21.     int l;
  22.     int r;
  23.     int pos;
  24.     dots* to_list;
  25. };
  26.  
  27. bool operator<(const heap_element& a, const heap_element& b)
  28. {
  29.  
  30.     if ((a.l < b.l))
  31.         return true;
  32.  
  33.     return false;
  34. }
  35.  
  36. class Heap
  37. {
  38.     std::vector<struct heap_element> h;
  39.     int heap_size;
  40.  
  41. public:
  42.     Heap();
  43.     void siftup(int sort_type, int pos);
  44.     void siftdown(int sort_type, int pos);
  45.     void my_swap(int i, int j);
  46.     void add(int sort_type, int l, int r, dots* to_list);
  47.     void del(int sort_type, int pos);
  48.     bool isempty();
  49.     heap_element* get_top();
  50.     int size();
  51.     void out();
  52. };
  53.  
  54. Heap::Heap()
  55. {
  56.     std::vector<struct heap_element> h;
  57.     heap_size = 0;
  58. }
  59.  
  60. void Heap::out(void)
  61. {
  62.  
  63.     for (int i = 0; i < heap_size; i++)
  64.     {
  65.         cout << "(" << h[i].l << "," << h[i].r << ") ";
  66.     }
  67.     cout << endl;
  68. }
  69.  
  70. int Heap::size()
  71. {
  72.     return this->heap_size;
  73. }
  74.  
  75. heap_element* Heap::get_top()
  76. {
  77.     return &h[0];
  78. }
  79.  
  80. bool Heap::isempty()
  81. {
  82.     if (heap_size == 0)
  83.         return true;
  84.     return false;
  85. }
  86.  
  87. void Heap::my_swap(int i, int j)
  88. {
  89.     heap_element buffer;
  90.  
  91.     buffer = h[i];
  92.     h[i] = h[j];
  93.     h[j] = buffer;
  94.  
  95.     h[i].pos = i;
  96.     h[j].pos = j;
  97.  
  98.     h[i].to_list->to_heap = i;
  99.     h[j].to_list->to_heap = j;
  100. }
  101.  
  102. void Heap::siftup(int sort_type, int pos)
  103. {
  104.     int curr = pos;
  105.     int parent = (curr - 1) / 2;
  106.  
  107.     while (parent >= 0 & curr > 0)
  108.     {
  109.         if (sort_type == heap_max & h[parent] < h[curr])
  110.             my_swap(parent, curr);
  111.  
  112.         if (sort_type == heap_min & h[curr] < h[parent])
  113.             my_swap(parent, curr);
  114.            
  115.         curr = parent;
  116.         parent = (curr - 1) / 2;
  117.     }
  118. }
  119.  
  120. void Heap::siftdown(int sort_type, int pos)
  121. {
  122.     int parent, max_child, min_child;
  123.  
  124.     int curr = pos;
  125.     int child_l = 2 * curr + 1;
  126.     int child_r = 2 * curr + 2;
  127.  
  128.     while (child_l < heap_size)
  129.     {
  130.        
  131.         if (sort_type == heap_max)
  132.         {
  133.             max_child = child_l;
  134.             if (child_r < heap_size & h[child_l] < h[child_r])
  135.                 max_child = child_r;
  136.      
  137.             if (h[curr] < h[max_child])
  138.                 my_swap(curr, max_child);
  139.      
  140.             curr = max_child;
  141.             child_l = 2 * curr + 1;
  142.             child_r = 2 * curr + 2;
  143.         }
  144.        
  145.         if (sort_type == heap_min)
  146.         {
  147.             if (child_l == heap_size - 1)
  148.                 min_child = child_l;
  149.             else if (h[child_r] < h[child_l])
  150.                 min_child = child_r;
  151.             else
  152.                 min_child = child_l;
  153.  
  154.  
  155.             if (h[min_child] < h[curr])
  156.             {
  157.                 my_swap(curr, min_child);
  158.             }
  159.             curr = min_child;
  160.             child_l = 2 * curr + 1;
  161.             child_r = 2 * curr + 2;
  162.         }
  163.  
  164.     }
  165. }
  166.  
  167. void Heap::add(int sort_type, int l, int r, dots* to_list)
  168. {
  169.  
  170.     this->heap_size++;
  171.  
  172.     heap_element vertex;
  173.     vertex.l = l;
  174.     vertex.r = r;
  175.     vertex.to_list = to_list;
  176.     vertex.pos = heap_size - 1;
  177.     h.push_back(vertex);
  178.  
  179.     to_list->to_heap = heap_size - 1;
  180.     siftup(sort_type, heap_size - 1);
  181. }
  182.  
  183. void Heap::del(int sort_type, int pos)
  184. {
  185.  
  186.     h[pos] = h[heap_size - 1];
  187.     h[pos].pos = pos;
  188.     h[pos].to_list->to_heap = pos;
  189.  
  190.     h.pop_back();
  191.     this->heap_size--;
  192.  
  193.     int parent = (pos - 1) / 2;
  194.  
  195.     if (sort_type == heap_max)
  196.     {
  197.         if (h[parent] < h[pos])
  198.             siftup(sort_type, pos);
  199.         else
  200.             siftdown(sort_type, pos);
  201.     }
  202.    
  203.     if (sort_type == heap_min)
  204.     {
  205.         if (h[pos] < h[parent])
  206.             siftup(sort_type, pos);
  207.         else
  208.             siftdown(sort_type, pos);
  209.     }
  210. }
  211.  
  212. int main()
  213. {
  214.  
  215.     Heap heap1;
  216.     Heap heap2;
  217.  
  218.     int count_requests;
  219.    
  220.     cin >> count_requests;
  221.    
  222.     dots requests[count_requests];
  223.     dots dot;
  224.     char c,x,y;
  225.     int a,b;
  226.    
  227.     cin >> c;
  228.     while (c == "Q")
  229.     {
  230.         cout << -1 << endl;
  231.         cin >> c;
  232.     }
  233.    
  234.     cin >> x >> y;
  235.     a = stoi(x);
  236.     b = stoi(y);
  237.    
  238.     dot.l = a;
  239.     dot.r = b;
  240.     dot.number_heap = 2;
  241.     requests[0] = dot;
  242.    
  243.     heap2.add(heap_min, a,b,&requests[0]);
  244.    
  245.     for (int = 0; i < count_requests; ++i)
  246.     {
  247.         cin >> c;
  248.         if (c == "Q")
  249.             heap.display_current_line();
  250.         else
  251.         {
  252.             cin >> x >> y;
  253.             int x = std::stoi(x);
  254.             int y = std::stoi(y);
  255.            
  256.             if (c == "D")
  257.             {
  258.                 flag = true;
  259.                 j = 0;
  260.                 while (flag)
  261.                 {
  262.                     if requests[j].l == x & requests[j].r == y
  263.                 }
  264.             }
  265.            
  266.             else
  267.             {
  268.                
  269.             }
  270.         }
  271.     }
  272.    
  273.     //a.l = 2;
  274.     //a.r = 2;
  275.     //requests[0] = a;
  276.     //heap.add(heap_max,2,2,&requests[0]);
  277.     //heap.out();
  278.    
  279.     return 0;  
  280. }
  281.  
  282.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement