vadimk772336

Для код ревью но WA5

Nov 3rd, 2021
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. struct heap_elements;
  5.  
  6. struct list_sections
  7. {
  8. int l;
  9. int r;
  10. int status;
  11. struct list_sections* next;
  12. struct list_sections* prev;
  13. int to_heap;
  14. };
  15.  
  16. struct heap_elements
  17. {
  18. int l;
  19. int r;
  20. int pos;
  21. list_sections* to_list;
  22. };
  23.  
  24. bool operator<(const heap_elements& a, const heap_elements& b)
  25. {
  26.  
  27. if ((a.r - a.l < b.r - b.l))
  28. return true;
  29. if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
  30. return true;
  31.  
  32. return false;
  33. }
  34.  
  35. class Heap
  36. {
  37. std::vector<struct heap_elements> massiv;
  38. int heap_size;
  39.  
  40. public:
  41. Heap();
  42. void siftup(int pos);
  43. void siftdown(int pos);
  44. void my_swap(int i, int j);
  45. void add(int, int, list_sections*);
  46. void delete_vertex(int pos);
  47. bool isempty();
  48. heap_elements* get_top();
  49. };
  50.  
  51. Heap::Heap()
  52. {
  53. std::vector<struct heap_elements> massiv;
  54. heap_size = 0;
  55. }
  56.  
  57. heap_elements* Heap::get_top()
  58. {
  59. return &massiv[0];
  60. }
  61.  
  62. bool Heap::isempty()
  63. {
  64. if (heap_size == 0)
  65. return true;
  66. return false;
  67. }
  68.  
  69. void Heap::my_swap(int i, int j)
  70. {
  71. heap_elements buffer;
  72.  
  73. buffer = massiv[i];
  74. massiv[i] = massiv[j];
  75. massiv[j] = buffer;
  76.  
  77. massiv[i].pos = i;
  78. massiv[j].pos = j;
  79.  
  80. massiv[i].to_list->to_heap = i;
  81. massiv[j].to_list->to_heap = j;
  82. }
  83.  
  84. void Heap::siftup(int pos)
  85. {
  86. int curr = pos;
  87. int parent = (curr - 1) / 2;
  88.  
  89. while (parent >= 0 & curr > 0)
  90. {
  91. if (massiv[parent] < massiv[curr])
  92. my_swap(parent, curr);
  93.  
  94. curr = parent;
  95. parent = (curr - 1) / 2;
  96. }
  97. }
  98.  
  99. void Heap::siftdown(int pos)
  100. {
  101. int parent, max_child;
  102.  
  103. int curr = pos;
  104. int child_l = 2 * curr + 1;
  105. int child_r = 2 * curr + 2;
  106.  
  107. while (child_l < heap_size)
  108. {
  109. max_child = child_l;
  110. if (child_r < heap_size & massiv[child_l] < massiv[child_r])
  111. max_child = child_r;
  112.  
  113. if (massiv[curr] < massiv[max_child])
  114. my_swap(curr, max_child);
  115.  
  116. curr = max_child;
  117. child_l = 2 * curr + 1;
  118. child_r = 2 * curr + 2;
  119. }
  120. }
  121.  
  122. void Heap::add(int l, int r, list_sections* to_list)
  123. {
  124.  
  125. heap_size++;
  126.  
  127. heap_elements vertex;
  128. vertex.l = l;
  129. vertex.r = r;
  130. vertex.to_list = to_list;
  131. vertex.pos = heap_size - 1;
  132. massiv.push_back(vertex);
  133.  
  134. to_list->to_heap = heap_size - 1;
  135. siftup(heap_size - 1);
  136. }
  137.  
  138. void Heap::delete_vertex(int pos)
  139. {
  140.  
  141. massiv[pos] = massiv[heap_size - 1];
  142. massiv[pos].pos = pos;
  143. massiv[pos].to_list->to_heap = pos;
  144.  
  145. massiv.pop_back();
  146. heap_size--;
  147.  
  148. int parent = (pos - 1) / 2;
  149. if (massiv[parent] < massiv[pos])
  150. siftup(pos);
  151. else
  152. siftdown(pos);
  153. }
  154.  
  155. class List
  156. {
  157. struct list_sections* head;
  158. int list_size;
  159.  
  160. public:
  161. List();
  162. list_sections* get_head();
  163. void add_head(int l, int r, int status, int to_heap);
  164. void add(int l, int r, int status, int to_heap, list_sections* section);
  165. void delete_section(list_sections* section);
  166. };
  167.  
  168. List::List()
  169. {
  170. head = NULL;
  171. list_size = 0;
  172. }
  173.  
  174. list_sections* List::get_head()
  175. {
  176. return head;
  177. }
  178.  
  179. void List::add_head(int l, int r, int status, int to_heap)
  180. {
  181. list_sections* buffer = new list_sections;
  182. buffer->prev = 0;
  183. buffer->l = l;
  184. buffer->r = r;
  185. buffer->status = status;
  186. buffer->next = head;
  187.  
  188. if (head != NULL)
  189. head->prev = buffer;
  190.  
  191. head = buffer;
  192. list_size++;
  193. }
  194.  
  195. void List::add(int l, int r, int status, int to_heap, list_sections* section)
  196. {
  197. list_sections* after_section = new list_sections;
  198. after_section->l = l;
  199. after_section->r = r;
  200. after_section->status = status;
  201. after_section->next = section->next;
  202. after_section->prev = section;
  203. after_section->to_heap = to_heap;
  204.  
  205. if (section->next != NULL)
  206. section->next->prev = after_section;
  207.  
  208. section->next = after_section;
  209. list_size++;
  210. }
  211.  
  212. void List::delete_section(list_sections* section)
  213. {
  214. if (section->next != NULL)
  215. section->next->prev = section->prev;
  216.  
  217. if (section->prev != NULL)
  218. section->prev->next = section->next;
  219. else
  220. head = section->next;
  221.  
  222. delete section;
  223. }
  224.  
  225.  
  226. void find_memory(Heap* heap, List* List, int K, int query_number, list_sections** requests)
  227. {
  228.  
  229. heap_elements* heap_top = heap->get_top();
  230.  
  231. if (!heap->isempty() & (heap_top->r - heap_top->l + 1) >= K)
  232. {
  233. std::cout << heap_top->l << std::endl;
  234.  
  235. if ((heap_top->r - heap_top->l + 1) == K)
  236. {
  237. heap_top->to_list->status = 0;
  238. requests[query_number] = heap_top->to_list;
  239. heap->delete_vertex(0);
  240. }
  241. else
  242. {
  243.  
  244. int new_l = heap_top->l;
  245. int r = new_l + K - 1;
  246. int status = 0;
  247. int to_heap = -1;
  248. list_sections* prev_head_section = heap_top->to_list->prev;
  249.  
  250. heap_top->l = new_l + K;
  251. heap_top->to_list->l = new_l + K;
  252.  
  253. if (prev_head_section != NULL)
  254. {
  255. List->add(new_l, r, status, to_heap, prev_head_section);
  256. requests[query_number] = prev_head_section;
  257. }
  258. else
  259. {
  260. List->add_head(new_l, r, status, to_heap);
  261. requests[query_number] = List->get_head();
  262. }
  263.  
  264. heap->siftdown(0);
  265. }
  266. }
  267. else
  268. {
  269. requests[query_number] = NULL;
  270. std::cout << -1 << std::endl;
  271. }
  272. }
  273.  
  274. void free_up_memory(Heap* heap, List* List, int q, int query_number, list_sections** 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_section(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_section(requests[q]->next);
  296. }
  297. }
  298.  
  299. heap->add(requests[q]->l, requests[q]->r, requests[q]);
  300. }
  301.  
  302. requests[query_number] = NULL;
  303. }
  304.  
  305.  
  306. int main()
  307. {
  308.  
  309. int N, M, K;
  310. heap_elements* heap_top;
  311.  
  312. Heap heap;
  313. List List;
  314.  
  315. std::cin >> N;
  316. std::cin >> M;
  317.  
  318. List.add_head(1, N, 1, 0);
  319. heap.add(1, N, List.get_head());
  320.  
  321. list_sections* requests[M];
  322.  
  323. for (int i = 0; i < M; ++i)
  324. {
  325. std::cin >> K;
  326. if (K > 0)
  327. find_memory(&heap, &List, K, i, requests);
  328. else
  329. free_up_memory(&heap, &List, -K - 1, i, requests);
  330. }
  331.  
  332. return 0;
  333. }
  334.  
Advertisement
Add Comment
Please, Sign In to add comment