Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. //
  2. // Created by larik on 11.10.2019.
  3. //
  4. #include <iostream>
  5. #include <vector>
  6. #include <utility>
  7. #include <algorithm>
  8.  
  9. class BinHeap {
  10. private:
  11.     std::vector<std::pair<int, std::pair<int, int>>> elems;
  12.  
  13.     int parent(int ii) {
  14.         return (ii - 1) / 2;
  15.     }
  16.  
  17.     int left(int ii) {
  18.         return (2 * ii + 1);
  19.     }
  20.  
  21.     int right(int ii) {
  22.         return (2 * ii + 2);
  23.     }
  24.  
  25.     void heap_up(int ii) {
  26.         if (ii && elems[parent(ii)].first > elems[ii].first) {
  27.             std::swap(elems[ii], elems[parent(ii)]);
  28.             heap_up(parent(ii));
  29.         }
  30.     }
  31.  
  32.     void heap_down(int ii) {
  33.         int ll = left(ii), rr = right(ii), cur = ii;
  34.         if (ll < size() && elems[ll].first < elems[cur].first) {
  35.             cur = ll;
  36.         }
  37.         if (rr < size() && elems[rr].first < elems[cur].first) {
  38.             cur = rr;
  39.         }
  40.         if (cur != ii) {
  41.             std::swap(elems[ii], elems[cur]);
  42.             heap_down(cur);
  43.         }
  44.     }
  45.  
  46. public:
  47.     int size() {
  48.         return elems.size();
  49.     }
  50.  
  51.     std::pair<int, std::pair<int, int>> root() {
  52.         return elems[0];
  53.     }
  54.  
  55.     void pop() {
  56.         elems[0] = elems.back();
  57.         elems.pop_back();
  58.         heap_down(0);
  59.     }
  60.  
  61.     void push(std::pair<int, std::pair<int, int>> elem) {
  62.         elems.push_back(elem);
  63.         heap_up(size() - 1);
  64.     }
  65. };
  66.  
  67. int main() {
  68.  
  69.     int nn, mm;
  70.     std::cin >> nn >> mm;
  71.     BinHeap heap;
  72.     std::vector<std::vector<int>> data(nn);
  73.     for (int i = 0; i < nn; ++i) {
  74.         data[i].resize(mm);
  75.         for (int j = 0; j < mm; ++j) {
  76.             int elem;
  77.             std::cin >> elem;
  78.             data[i][j] = elem;
  79.         }
  80.     }
  81.     std::vector<int> result;
  82.     for (int i = 0; i < nn; ++i) {
  83.         heap.push(std::pair(data[i][0], std::pair(i, 0)));
  84.     }
  85.     while (heap.size() > 0) {
  86.         std::pair<int, std::pair<int, int>> min;
  87.         min = heap.root();
  88.         heap.pop();
  89.         std::cout << min.first << ' ';
  90.         int ii = min.second.first, jj = min.second.second;
  91.         if (jj < mm - 1) {
  92.             heap.push(std::pair(data[ii][jj + 1], std::pair(ii, jj + 1)));
  93.         }
  94.     }
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement