vadimk772336

Собрана но пока не ворк верно

Oct 30th, 2021
2,033
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4.  
  5. using namespace std;
  6.  
  7. class Heap
  8. {
  9.     std::vector<int> h;
  10.     std::vector<int> ID_to_HeapIdx;
  11.     int heap_size;
  12.     int curr_ID;
  13.  
  14. public:
  15.     Heap();
  16.     void siftup(int ID, std::vector<int>& HeapIdx_to_ID);
  17.     void siftdown(int ID, std::vector<int>& HeapIdx_to_ID);
  18.     void add(int vertex, int ID, std::vector<int>& HeapIdx_to_ID);
  19.     void delete_vertex(int ID, std::vector<int>& HeapIdx_to_ID);
  20.     bool isempty();
  21.     void out();
  22.     int get_root();
  23. };
  24.  
  25. Heap::Heap()
  26. {
  27.     std::vector<int> h;
  28.     heap_size = 0;
  29.     curr_ID = 0;
  30.     std::vector<int> ID_to_HeapIdx;
  31. }
  32.  
  33. int Heap::get_root()
  34. {
  35.     if (heap_size > 0)
  36.         return h[0];
  37.     return -1;
  38. }
  39.  
  40. bool Heap::isempty()
  41. {
  42.     if (heap_size == 0)
  43.         return true;
  44.     return false;
  45. }
  46.  
  47. void Heap::siftup(int ID, std::vector<int>& HeapIdx_to_ID)
  48. {
  49.     int curr, parent, tmp;
  50.     curr = heap_size - 1;
  51.     parent = (curr - 1);
  52.     for (int i = 0; i < HeapIdx_to_ID.size(); i++)
  53.  
  54.         for (int i = 0; i < ID_to_HeapIdx.size(); i++)
  55.  
  56.             while (parent >= 0 && curr > 0)
  57.             {
  58.  
  59.                 if (h[parent] < h[curr])
  60.                 {
  61.  
  62.                     int buff = h[curr];
  63.                     h[curr] = h[parent];
  64.                     h[parent] = buff;
  65.  
  66.                     tmp = HeapIdx_to_ID[parent];
  67.                     HeapIdx_to_ID[parent] = HeapIdx_to_ID[curr];
  68.                     HeapIdx_to_ID[curr] = tmp;
  69.  
  70.  
  71.                     tmp = ID_to_HeapIdx[HeapIdx_to_ID[parent]];
  72.                     ID_to_HeapIdx[HeapIdx_to_ID[parent]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
  73.                     ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;
  74.                 }
  75.                 curr = parent;
  76.                 parent = (curr - 1);
  77.             }
  78. }
  79.  
  80. void Heap::add(int vertex, int ID, std::vector<int>& HeapIdx_to_ID)
  81. {
  82.  
  83.     h.push_back(vertex);
  84.     ID_to_HeapIdx.push_back(heap_size);
  85.     HeapIdx_to_ID.push_back(ID);
  86.     heap_size++;
  87.     siftup(ID, HeapIdx_to_ID);
  88. }
  89.  
  90. void Heap::siftdown(int ID, std::vector<int>& HeapIdx_to_ID)
  91. {
  92.     int parent, max_child, tmp, buff;
  93.  
  94.     int curr = ID_to_HeapIdx[ID];
  95.     int child_l = 2 * curr + 1;
  96.     int child_r = 2 * curr + 2;
  97.  
  98.     if (h[child_r] < h[child_l])
  99.         max_child = child_l;
  100.     else
  101.         max_child = child_r;
  102.  
  103.     while (child_l < heap_size)
  104.     {
  105.         if (child_l == heap_size - 1)
  106.             max_child = child_l;
  107.         else if (h[child_r] < h[child_l])
  108.             max_child = child_l;
  109.         else
  110.             max_child = child_r;
  111.  
  112.         if (h[curr] < h[max_child])
  113.         {
  114.  
  115.             buff = h[curr];
  116.             h[curr] = h[max_child];
  117.             h[max_child] = buff;
  118.  
  119.             tmp = HeapIdx_to_ID[max_child];
  120.             HeapIdx_to_ID[max_child] = HeapIdx_to_ID[curr];
  121.             HeapIdx_to_ID[curr] = tmp;
  122.  
  123.             tmp = ID_to_HeapIdx[HeapIdx_to_ID[max_child]];
  124.             ID_to_HeapIdx[HeapIdx_to_ID[max_child]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
  125.             ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;
  126.         }
  127.         curr = max_child;
  128.         child_l = 2 * curr + 1;
  129.         child_r = 2 * curr + 2;
  130.     }
  131. }
  132.  
  133.  
  134. void Heap::delete_vertex(int ID, std::vector<int>& HeapIdx_to_ID)
  135. {
  136.     int pos = ID_to_HeapIdx[ID];
  137.     h[pos] = h[heap_size - 1];
  138.     h.pop_back();
  139.     heap_size--;
  140.     siftdown(ID, HeapIdx_to_ID);
  141. }
  142.  
  143.  
  144. void Heap::out(void)
  145. {
  146.  
  147.     for (int i = 0; i < heap_size; i++)
  148.     {
  149.         cout << h[i] << " ";
  150.     }
  151.     cout << endl;
  152. }
  153.  
  154. int main()
  155. {
  156.     Heap heap1;
  157.     Heap heap2;
  158.     std::vector<int> HeapIdx1_to_ID;
  159.     std::vector<int> HeapIdx2_to_ID;
  160.     char c;
  161.  
  162.     int count = 0;
  163.     int ID1 = -1;
  164.     int ID2 = -1;
  165.     deque<int> deq1;
  166.     deque<int> deq2;
  167.  
  168.     int N, M, K, ID, root1_ID, root2_ID;
  169.     N = 7;
  170.     M = 4;
  171.     K = 2;
  172.  
  173.  
  174.     int ID1toID2[N];
  175.     int ID2toID1[N];
  176.  
  177.     int R = 0, L = 0;
  178.     int a[N] = { 4, 2, 1, 3, 6, 5, 7 };
  179.  
  180.     for (int i = 0; i < M; ++i)
  181.     {
  182.         cin >> c;
  183.         if (c == 'R')
  184.         {
  185.             count++;
  186.             R++;
  187.  
  188.             if (count < K)
  189.             {
  190.                 ID1++;
  191.                 heap1.add(a[R], ID1, HeapIdx1_to_ID);
  192.                 deq1.push_back(ID1);
  193.                 cout << "-1" << endl;
  194.             }
  195.             if (count == K)
  196.             {
  197.                 ID1++;
  198.                 heap1.add(a[R], ID1, HeapIdx1_to_ID);
  199.                 deq1.push_back(ID1);
  200.                 cout << heap1.get_root() << endl;
  201.             }
  202.             if (count > K)
  203.             {
  204.  
  205.                 if (a[R] > heap1.get_root())
  206.                 {
  207.                     ID2++;
  208.                     heap2.add(a[R], ID2, HeapIdx2_to_ID);
  209.                     deq2.push_back(ID2);
  210.                     cout << heap1.get_root() << endl;
  211.                 }
  212.  
  213.                 else
  214.  
  215.                 {
  216.  
  217.                     root1_ID = HeapIdx1_to_ID[0];
  218.                     heap1.delete_vertex(root1_ID, HeapIdx1_to_ID);
  219.  
  220.  
  221.                     ID1++;
  222.                     heap1.add(a[R], ID1, HeapIdx1_to_ID);
  223.                     deq1.push_back(ID1);
  224.  
  225.                     ID2++;
  226.                     int root1ID = heap1.get_root();
  227.                     heap2.add(root1ID, ID2, HeapIdx2_to_ID);
  228.                     deq2.push_back(ID2);
  229.                     deq1[root1ID] = -ID2;
  230.                     ID1toID2[root1ID] = ID2;
  231.                     ID2toID1[ID2] = root1ID;
  232.                 }
  233.             }
  234.         }
  235.         else
  236.         {
  237.             L--;
  238.             count--;
  239.             if (count < K)
  240.             {
  241.                 ID = deq1[0];
  242.                 if (ID < 0)
  243.                 {
  244.                     deq1.pop_front();
  245.  
  246.                     heap2.delete_vertex(-ID, HeapIdx2_to_ID);
  247.                     cout << "-1" << endl;
  248.                 }
  249.                 else
  250.                 {
  251.                     deq1.pop_front();
  252.                     heap1.delete_vertex(ID, HeapIdx1_to_ID);
  253.                     cout << "-1" << endl;
  254.                 }
  255.             }
  256.             if (count >= K)
  257.             {
  258.                 ID = deq1[0];
  259.  
  260.                 if (ID < 0)
  261.                 {
  262.                     deq1.pop_front();
  263.  
  264.                     heap2.delete_vertex(-ID, HeapIdx2_to_ID);
  265.                 }
  266.                 else
  267.                 {
  268.                     deq1.pop_front();
  269.                     heap1.delete_vertex(ID, HeapIdx1_to_ID);
  270.                 }
  271.  
  272.                 ID1++;
  273.                 heap1.add(heap2.get_root(), ID1, HeapIdx1_to_ID);
  274.  
  275.  
  276.                 int ID_top2 = HeapIdx2_to_ID[0];
  277.                 heap2.delete_vertex(ID_top2, HeapIdx2_to_ID);
  278.  
  279.  
  280.                 deq1[ID2toID1[ID_top2]] = ID2toID1[ID_top2];
  281.                 cout << heap1.get_root() << endl;
  282.             }
  283.         }
  284.     }
  285.  
  286. return 0;
  287. }
  288.  
Advertisement
Add Comment
Please, Sign In to add comment