vadimk772336

то же самое но без сиаут

Nov 3rd, 2021 (edited)
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. #include <fstream>
  5.  
  6. enum sort_type
  7. {
  8. heap_max = 0,
  9. heap_min = 1
  10. };
  11.  
  12. struct heap_elements
  13. {
  14. int value;
  15. int own_ID;
  16. };
  17.  
  18. bool operator<(const heap_elements& a, const heap_elements& b)
  19. {
  20. return (a.value < b.value);
  21. }
  22.  
  23. class Heap
  24. {
  25. std::vector<struct heap_elements> h;
  26. int heap_size;
  27.  
  28. public:
  29. Heap();
  30. bool isempty();
  31. heap_elements get_top();
  32. void siftup(int sort_type, std::vector<int>& ID_to_Index);
  33. void siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index);
  34. void swap(int i, int j, std::vector<int>& ID_to_Index);
  35. void add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index);
  36. void delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index);
  37. void out();
  38. };
  39.  
  40. Heap::Heap()
  41. {
  42. std::vector<struct heap_elements> h;
  43. heap_size = 0;
  44. }
  45.  
  46. heap_elements Heap::get_top()
  47. {
  48. return h[0];
  49. }
  50.  
  51. bool Heap::isempty()
  52. {
  53. if (heap_size == 0)
  54. return true;
  55. return false;
  56. }
  57.  
  58. void Heap::swap(int i, int j, std::vector<int>& ID_to_Index)
  59. {
  60. heap_elements buff;
  61. buff = h[i];
  62. h[i] = h[j];
  63. h[j] = buff;
  64.  
  65. ID_to_Index[h[i].own_ID] = i; //На местах в этом массиве лежат айди этой кучи все ок
  66. ID_to_Index[h[j].own_ID] = j;
  67. }
  68.  
  69. void Heap::siftup(int sort_type, std::vector<int>& ID_to_Index)
  70. {
  71. int curr = heap_size - 1;
  72. int parent = (curr - 1) / 2;
  73. while (curr > 0 & parent >= 0)
  74. {
  75. if (sort_type == heap_max & h[parent] < h[curr])
  76. swap(parent, curr, ID_to_Index);
  77.  
  78. if (sort_type == heap_min & h[curr] < h[parent])
  79. swap(parent, curr, ID_to_Index);
  80.  
  81. curr = parent;
  82. parent = (curr - 1) / 2;
  83. }
  84. }
  85.  
  86. void Heap::siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index)
  87. {
  88.  
  89. int parent, max_child, min_child;
  90.  
  91. int curr = pos;
  92. int child_l = 2 * curr + 1;
  93. int child_r = 2 * curr + 2;
  94.  
  95. // max_child = (h[child_r] < h[child_l]) ? child_l : child_r;
  96. // min_child = (h[child_r] > h[child_l]) ? child_l : child_r;
  97.  
  98. /*
  99. if (h[child_r] < h[child_l])
  100. max_child = child_l;
  101. else
  102. max_child = child_r;
  103. */
  104.  
  105. while (child_l < heap_size)
  106. {
  107. if (sort_type == heap_max)
  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. swap(curr, max_child, ID_to_Index);
  118.  
  119. curr = max_child;
  120. child_l = 2 * curr + 1;
  121. child_r = 2 * curr + 2;
  122. }
  123.  
  124. if (sort_type == heap_min)
  125. {
  126. if (child_l == heap_size - 1)
  127. min_child = child_l;
  128. else if (h[child_r] < h[child_l])
  129. min_child = child_r;
  130. else
  131. min_child = child_l;
  132.  
  133. if (h[min_child] < h[curr])
  134. swap(curr, min_child, ID_to_Index);
  135.  
  136. curr = min_child;
  137. child_l = 2 * curr + 1;
  138. child_r = 2 * curr + 2;
  139. }
  140. }
  141. }
  142.  
  143.  
  144. void Heap::add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index)
  145. {
  146. heap_elements vertex;
  147. vertex.value = value;
  148. vertex.own_ID = ID;
  149.  
  150. h.push_back(vertex);
  151.  
  152.  
  153. //Если это новое добавление, то надо делать пушбек,
  154. //а если старое, то надо просто на место ID написать heap_size
  155.  
  156. if (ID < ID_to_Index.size()) {
  157. ID_to_Index[ID] = heap_size;
  158. }
  159. else {
  160. ID_to_Index.push_back(heap_size); //должно быть общее у двух куч
  161. }
  162. heap_size++;
  163. siftup(sort_type, ID_to_Index);
  164. }
  165.  
  166. void Heap::delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index)
  167. {
  168.  
  169. int pos = ID_to_Index[ID];
  170.  
  171.  
  172. swap(pos, heap_size - 1, ID_to_Index); //Можно не делать свап
  173. h.pop_back();
  174. heap_size--;
  175. ID_to_Index[ID] = -1; //мб убрать
  176. siftdown(sort_type, pos, ID_to_Index);
  177. }
  178.  
  179.  
  180.  
  181.  
  182.  
  183. int main()
  184. {
  185.  
  186.  
  187. ifstream ifs("com.txt");
  188. ofstream out("results.txt");
  189. int count_tests;
  190. ifs >> count_tests;
  191.  
  192. for (int k = 0; k < count_tests; k++)
  193. {
  194.  
  195. Heap heap1;
  196. Heap heap2;
  197.  
  198. std::vector<int> ID_to_Index;
  199. int NumberHeap;
  200. int curr_ID = 0;
  201. char c;
  202.  
  203. int N, M, K, ID, ID_root1, root2_ID, ID_root2, count = 1;
  204. ifs >> N;
  205. ifs >> M;
  206. int answers[M];
  207. K = 5;
  208. int R = 0, L = 0;
  209. int a[N];
  210. for (int j = 0; j < N; j++)
  211. ifs >> a[j];
  212.  
  213. int ID_to_HeapNumber[N]; //При перебрасывании в другую кучу
  214.  
  215. heap1.add(heap_max, curr_ID, a[0], ID_to_Index);
  216. ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  217. curr_ID++;
  218.  
  219.  
  220.  
  221. for (int i = 0; i < M; ++i)
  222. {
  223.  
  224. // cin >> c;
  225. ifs >> c;
  226.  
  227. if (c == 'R')
  228. {
  229. count++;
  230. R++;
  231.  
  232.  
  233. if (count < K)
  234. {
  235.  
  236. heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  237. ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  238. curr_ID++;
  239.  
  240. answers[i] = -1;
  241.  
  242.  
  243.  
  244. }
  245.  
  246. if (count == K)
  247. {
  248.  
  249. heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  250. ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  251. curr_ID++;
  252.  
  253. answers[i] = heap1.get_top().value;
  254.  
  255. }
  256.  
  257. if (count > K)
  258. {
  259.  
  260. if (a[R] > heap1.get_top().value)
  261. {
  262.  
  263. heap2.add(heap_min, curr_ID, a[R], ID_to_Index);
  264. ID_to_HeapNumber[curr_ID] = 2; //Обновляю ID_to_HeapNumber
  265. curr_ID++;
  266.  
  267. answers[i] = heap1.get_top().value;
  268.  
  269.  
  270. }
  271.  
  272. if (a[R] <= heap1.get_top().value)
  273.  
  274. {
  275.  
  276. heap_elements root1, root2;
  277.  
  278. //Запоминаю корень 1 кучи
  279. root1 = heap1.get_top();
  280. ID_root1 = root1.own_ID;
  281.  
  282. // удаляю корень 1 кучи из 1 кучи
  283. heap1.delete_vertex(heap_max, ID_root1, ID_to_Index);
  284.  
  285.  
  286.  
  287. // Добавляю корень 1 кучи во 2 кучу не меняя ID
  288. heap2.add(heap_min, ID_root1, root1.value, ID_to_Index);
  289. ID_to_HeapNumber[ID_root1] = 2; //Обновляю ID_to_HeapNumber
  290.  
  291.  
  292.  
  293.  
  294. //Добавляю в 1 кучу a[R] меняя айди
  295. heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  296. ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  297. curr_ID++;
  298.  
  299.  
  300. answers[i] = heap1.get_top().value;
  301.  
  302. }
  303. }
  304. }
  305. else
  306. {
  307. L++;
  308. count--;
  309.  
  310.  
  311.  
  312. ID = L - 1;
  313. NumberHeap = ID_to_HeapNumber[ID];
  314.  
  315.  
  316. //Если лежит в куче1 то удаляем там, иначе во 2
  317. if (NumberHeap == 1)
  318. heap1.delete_vertex(heap_max, ID, ID_to_Index);
  319. else
  320. heap2.delete_vertex(heap_min, ID, ID_to_Index);
  321.  
  322.  
  323.  
  324.  
  325. if (count >= K)
  326. {
  327.  
  328.  
  329. //Если удалили из 2 кучи, то первая не пострадала и просто принтим
  330. if (NumberHeap == 2)
  331. {
  332.  
  333. answers[i] = heap1.get_top().value;
  334. }
  335.  
  336. else
  337. {
  338. //Запоминаю вершину кучи2
  339. heap_elements root2 = heap2.get_top();
  340. root2_ID = root2.own_ID;
  341.  
  342. //Удаляем вершину кучи2, т.к. теперь она в куче1
  343. heap2.delete_vertex(heap_min, root2_ID, ID_to_Index);
  344.  
  345.  
  346.  
  347. //cout
  348.  
  349. //Добавляем вершину кучи2 в кучу1 не меняя индекс чтобы стало K штук
  350. heap1.add(heap_max, root2_ID, root2.value, ID_to_Index);
  351. ID_to_HeapNumber[root2_ID] = 1; //Обновляю ID_to_HeapNumber
  352.  
  353. answers[i] = heap1.get_top().value;
  354.  
  355.  
  356. }
  357. }
  358. else
  359. {
  360. answers[i] = -1;
  361. }
  362. }
  363. }
  364.  
  365. cout << endl;
  366. int y;
  367. int true_ans[M];
  368. /*
  369. for (int j = 0; j < M; j++)
  370. {
  371. out << answers[j] << " ";
  372. }
  373. */
  374. out << endl;
  375. for (int j = 0; j < M; j++)
  376. {
  377. ifs >> y;
  378. true_ans[j] = y;
  379. //out << y << " ";
  380. }
  381.  
  382. out << endl;
  383. for (int j = 0; j < M; j++)
  384. {
  385.  
  386. if (true_ans[j] != answers[j]) {
  387. out << "WA" << j << " ";
  388. cout << "Неверный ответ на тесте " << k << endl;
  389. }
  390. else
  391. out << "1 ";
  392. }
  393. out << endl;
  394. }
  395.  
  396.  
  397. return 0;
  398. }
Add Comment
Please, Sign In to add comment