vadimk772336

Тестирование (файл)

Oct 28th, 2021 (edited)
310
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. using namespace std;
  5.  
  6. struct heap_elements;
  7.  
  8. struct list_segments
  9. {
  10.     int l;
  11.     int r;
  12.     int status;
  13.     struct list_segments* next;
  14.     struct list_segments* prev;
  15.     int to_heap;
  16. };
  17.  
  18. struct heap_elements
  19. {
  20.     int l;
  21.     int r;
  22.     int pos;
  23.     list_segments* to_list;
  24. };
  25.  
  26. bool operator<(const heap_elements& a, const heap_elements& b)
  27. {
  28.  
  29.     if ((a.r - a.l < b.r - b.l))
  30.         return true;
  31.     if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
  32.         return true;
  33.  
  34.     return false;
  35. }
  36.  
  37. class Heap
  38. {
  39.     std::vector<struct heap_elements> h;
  40.     int heap_size;
  41.  
  42. public:
  43.     Heap();
  44.     void siftup();
  45.     void siftdown(int pos);
  46.     void add(int, int, list_segments*);
  47.     void delete_vertex(int pos);
  48.     bool isempty();
  49.     heap_elements* get_head();
  50. };
  51.  
  52. Heap::Heap()
  53. {
  54.     std::vector<struct heap_elements> h;
  55.     heap_size = 0;
  56. }
  57.  
  58. heap_elements* Heap::get_head()
  59. {
  60.     return &h[0];
  61. }
  62.  
  63. bool Heap::isempty()
  64. {
  65.     if (heap_size == 0)
  66.         return true;
  67.     return false;
  68. }
  69.  
  70. void Heap::siftup()
  71. {
  72.     int curr, parent;
  73.     curr = heap_size - 1;
  74.     parent = (curr - 1) / 2;
  75.     while (parent >= 0 && curr > 0)
  76.     {
  77.         if (h[parent] < h[curr])
  78.         {
  79.             heap_elements buff = h[curr];
  80.             h[curr] = h[parent];
  81.             h[parent] = buff;
  82.  
  83.             h[curr].pos = curr;
  84.             h[parent].pos = parent;
  85.  
  86.             h[curr].to_list->to_heap = curr;
  87.             h[parent].to_list->to_heap = parent;
  88.         }
  89.         curr = parent;
  90.         parent = (curr - 1) / 2;
  91.     }
  92. }
  93.  
  94. void Heap::siftdown(int pos)
  95. {
  96.     int parent, max_child;
  97.  
  98.     int curr = pos;
  99.     int child_l = 2 * curr + 1;
  100.     int child_r = 2 * curr + 2;
  101.  
  102.     if (h[child_r] < h[child_l])
  103.         max_child = child_l;
  104.     else
  105.         max_child = child_r;
  106.  
  107.     while (child_l < heap_size)
  108.     {
  109.         if (child_l == heap_size - 1)
  110.             max_child = child_l;
  111.         else if (h[child_r] < h[child_l])
  112.             max_child = child_l;
  113.         else
  114.             max_child = child_r;
  115.  
  116.         if (h[curr] < h[max_child])
  117.         {
  118.             heap_elements buff = h[curr];
  119.             h[curr] = h[max_child];
  120.             h[max_child] = buff;
  121.  
  122.             h[curr].pos = curr;
  123.             h[max_child].pos = max_child;
  124.  
  125.             h[curr].to_list->to_heap = curr;
  126.             h[max_child].to_list->to_heap = max_child;
  127.         }
  128.  
  129.         curr = max_child;
  130.         child_l = 2 * curr + 1;
  131.         child_r = 2 * curr + 2;
  132.     }
  133. }
  134.  
  135. void Heap::add(int l, int r, list_segments* to_list)
  136. {
  137.  
  138.     heap_elements vertex;
  139.     vertex.l = l;
  140.     vertex.r = r;
  141.     vertex.to_list = to_list;
  142.  
  143.     h.push_back(vertex);
  144.     h[heap_size].pos = heap_size;
  145.  
  146.     if (h[heap_size].to_list != NULL)
  147.         h[heap_size].to_list->to_heap = heap_size;
  148.  
  149.     heap_size++;
  150.     siftup();
  151. }
  152.  
  153. void Heap::delete_vertex(int pos)
  154. {
  155.     h[pos] = h[heap_size - 1];
  156.     h.pop_back();
  157.     heap_size--;
  158.     siftdown(pos);
  159. }
  160.  
  161. class LIST_SEGMENTS
  162. {
  163.     struct list_segments* Head;
  164.     int count;
  165.  
  166. public:
  167.     LIST_SEGMENTS();
  168.     list_segments* get_head();
  169.     void add(int, int, int, int, list_segments*);
  170.     void delete_segment(list_segments* segment);
  171.     void add_head(int, int, int, int);
  172. };
  173.  
  174. LIST_SEGMENTS::LIST_SEGMENTS()
  175. {
  176.     Head = NULL;
  177.     count = 0;
  178. }
  179.  
  180. void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
  181. {
  182.     list_segments* buff = new list_segments;
  183.     buff->prev = 0;
  184.     buff->l = l;
  185.     buff->r = r;
  186.     buff->status = status;
  187.     buff->next = Head;
  188.  
  189.     if (Head != NULL)
  190.         Head->prev = buff;
  191.  
  192.     Head = buff;
  193.     count++;
  194. }
  195.  
  196. void LIST_SEGMENTS::add(int l, int r, int status, int to_heap, list_segments* segment)
  197. {
  198.     list_segments* after_segment = new list_segments;
  199.     after_segment->l = l;
  200.     after_segment->r = r;
  201.     after_segment->status = status;
  202.     after_segment->next = segment->next;
  203.     after_segment->prev = segment;
  204.     after_segment->to_heap = to_heap;
  205.  
  206.     if (segment->next != NULL)
  207.         segment->next->prev = after_segment;
  208.  
  209.     segment->next = after_segment;
  210.     count++;
  211. }
  212.  
  213. void LIST_SEGMENTS::delete_segment(list_segments* segment)
  214. {
  215.     if (segment->next != NULL)
  216.         segment->next->prev = segment->prev;
  217.     if (segment->prev != NULL)
  218.         segment->prev->next = segment->next;
  219.     else
  220.         Head = segment->next;
  221.     delete segment;
  222. }
  223.  
  224. list_segments* LIST_SEGMENTS::get_head()
  225. {
  226.     return Head;
  227. }
  228.  
  229. void find_memory(Heap* heap, LIST_SEGMENTS* List, int K, int query_number,
  230.     std::vector<int>& answers, list_segments** requests)
  231. {
  232.     int old_l;
  233.     heap_elements* heap_head;
  234.  
  235.     heap_head = heap->get_head();
  236.     if (!heap->isempty() & (heap_head->r - heap_head->l + 1) >= K)
  237.     {
  238.         if ((heap_head->r - heap_head->l + 1) == K)
  239.         {
  240.             heap_head->to_list->status = 0;
  241.             requests[query_number] = heap_head->to_list;
  242.             answers.push_back(heap_head->l);
  243.             heap->delete_vertex(0);
  244.         }
  245.         else
  246.         {
  247.             old_l = heap_head->l;
  248.             heap_head->l = old_l + K;
  249.             heap_head->to_list->l = old_l + K;
  250.  
  251.             if (heap_head->to_list->prev != NULL)
  252.             {
  253.                 List->add(old_l, old_l + K - 1, 0, -1, heap_head->to_list->prev);
  254.                 requests[query_number] = heap_head->to_list->prev;
  255.             }
  256.             else
  257.             {
  258.                 List->add_head(old_l, old_l + K - 1, 0, -1);
  259.                 requests[query_number] = List->get_head();
  260.             }
  261.  
  262.             heap->siftdown(0);
  263.             answers.push_back(old_l);
  264.         }
  265.     }
  266.     else
  267.     {
  268.         requests[query_number] = NULL;
  269.         answers.push_back(-1);
  270.     }
  271. }
  272.  
  273. void free_up_memory(Heap* heap, LIST_SEGMENTS* List, int q, int query_number,
  274.     std::vector<int>& answers, list_segments** requests)
  275. {
  276.  
  277.     if (requests[q] != NULL)
  278.     {
  279.         requests[q]->status = 1;
  280.         if (requests[q]->prev != NULL)
  281.         {
  282.             if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
  283.             {
  284.                 requests[q]->l = requests[q]->prev->l;
  285.                 heap->delete_vertex(requests[q]->prev->to_heap);
  286.                 List->delete_segment(requests[q]->prev);
  287.             }
  288.         }
  289.         if (requests[q]->next != NULL)
  290.         {
  291.             if (requests[q]->next->status == 1 & requests[q]->next->l - 1 == requests[q]->r)
  292.             {
  293.                 requests[q]->r = requests[q]->next->r;
  294.                 heap->delete_vertex(requests[q]->next->to_heap);
  295.                 List->delete_segment(requests[q]->next);
  296.             }
  297.         }
  298.  
  299.         heap->add(requests[q]->l, requests[q]->r, requests[q]);
  300.         requests[query_number] = requests[q];
  301.         requests[q] = NULL;
  302.     }
  303.     else
  304.     {
  305.         requests[query_number] = NULL;
  306.     }
  307. }
  308.  
  309.  
  310.  
  311.  
  312. int main()
  313. {
  314.    
  315.     /*
  316.     -9
  317.     6 8 2 3 -1 3 3 -5 2 2 //1 3 -1 -1 1 -1
  318.     1 7 2 2 1 1 -4 -1 -3 //-1 -1 1 -1
  319.     6 9 2 2 2 -1 -3 -2  2 2 2 // 1 3 5 1 3 5
  320.     6 2 3 -1 //1,-1,1,3
  321.     6 7 6 6-2-1 2 4 -5
  322.     10 14 8 2 -2 5 -4 -4 -1 4 4 2 -8 -10 -9 10 //1 9 -1 1 5 9 1
  323.     1 1 1  // 1
  324.     1 2 1 2   //1 -1
  325.     1 9 2 -1 1 1 -1 2 1 -3 1 //-1 1 -1 -1 -1 1
  326.  
  327.     */
  328.     int N, M, K, q, old_l;
  329.  
  330.     int count_tests;
  331.     ifstream ifs("tests.txt");
  332.     ifs >> count_tests;
  333.     ofstream out("results.txt");
  334.  
  335.     for (int i = 0; i < count_tests; ++i)
  336.     {
  337.         ifs >> N;
  338.         ifs >> M;
  339.         Heap heap;
  340.         LIST_SEGMENTS List;
  341.         heap_elements* heap_head;
  342.         std::vector<int> answers;
  343.    
  344.         List.add_head(1, N, 1, 0);
  345.         heap.add(1, N, List.get_head());
  346.         list_segments* requests[M];
  347.         for (int query_number = 0; query_number < M; ++query_number)
  348.         {
  349.             ifs >> K;
  350.             if (K > 0)
  351.                 find_memory(&heap, &List, K, query_number, answers, requests);
  352.             else
  353.             {
  354.                 q = -K - 1;
  355.                 free_up_memory(&heap, &List, q, query_number, answers, requests);
  356.             }
  357.         }
  358.  
  359.         for (int i = 0; i < answers.size(); ++i){
  360.             out << answers[i] << ' ';
  361.             cout << answers[i] << " ";
  362.         }
  363.         cout << endl;
  364.         out << '\n';
  365.     }
  366.  
  367.     return 0;
  368. }
  369.  
RAW Paste Data