SHARE
TWEET

Untitled

a guest Jun 25th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. ifstream fin;
  8. ofstream fout;
  9.  
  10. struct sValue{
  11.     sValue(int k, int v)
  12.     {
  13.         key = k; data = v;
  14.     };
  15.     int key;
  16.     int data;
  17. };
  18.  
  19. void quickSort(vector<sValue> &a, int l, int r);
  20.  
  21. int leftChild(int i);
  22. int rightChild(int i);
  23. int parent(int i);
  24.  
  25. void insert(vector<sValue> &heap, sValue value, int &N);
  26. void heapify(vector<sValue>& heap, int i, int type);
  27.  
  28. sValue extract(vector<sValue> &heap, int &N);
  29.  
  30.  
  31. int main()
  32. {
  33.     fin.open("input.txt", ios_base::in);
  34.     fout.open("output.txt", ios_base::out);
  35.  
  36.     int N, M, tmp,
  37.         count = 0;
  38.  
  39.     fin >> N >> M;
  40.  
  41.     int countIn = N;
  42.  
  43.     vector<sValue> heap;
  44.  
  45.     for (int i = 0; i < N; i++)
  46.     {
  47.         fin >> tmp;
  48.         insert(heap, sValue(i, tmp), count);
  49.     }
  50.  
  51.     heapify(heap, 0, 1);
  52.  
  53.     for (int i = 0; i < M; i++)
  54.     {
  55.         sValue left  = extract(heap,count),
  56.                right = extract(heap,count);
  57.  
  58.         tmp = left.data + right.data;
  59.    
  60.         insert(heap, sValue(++countIn, tmp), count);
  61.     }
  62.  
  63.     quickSort(heap, 0, heap.size() - 1);
  64.  
  65.     for (int i = 0; i < heap.size(); i++)
  66.         fout << heap[i].data << " ";
  67.  
  68.     fin.close();
  69.     fout.close();
  70.  
  71.     return 0;
  72. }
  73.  
  74. int leftChild(int i)
  75. {
  76.     return 2 * i + 1;
  77. }
  78.  
  79. int rightChild(int i)
  80. {
  81.     return 2 * i + 2;
  82. }
  83.  
  84. int parent(int i)
  85. {
  86.     return (i-1) / 2;
  87. }
  88.  
  89. void quickSort(vector<sValue> &heap, int l, int r)
  90. {
  91.     int x = heap[(l+r) / 2].key;
  92.     int left = l;
  93.     int right = r;
  94.     while (left <= right)
  95.     {
  96.         for (;heap[left].key < x; left++);
  97.         for (;heap[right].key > x; right--);
  98.  
  99.         if (left <= right)
  100.             swap(heap[left++], heap[right--]);
  101.  
  102.     }
  103.     if (l < right)
  104.         quickSort(heap, l, right);
  105.     if (left < r)
  106.         quickSort(heap, left, r);
  107. }
  108.  
  109. void heapify(vector<sValue>& heap, int i, int type)
  110. {
  111.     int l,r,largest;
  112.    
  113.     while (true)
  114.     {
  115.         l = leftChild(i);
  116.         r = rightChild(i);
  117.         largest = i;
  118.        
  119.         if (type)
  120.         {  
  121.             if(l < heap.size() && heap[l].data == heap[largest].data && heap[l].key < heap[largest].key)
  122.                 largest = l;
  123.                
  124.             if(r < heap.size() && heap[r].data == heap[largest].data && heap[r].key < heap[largest].key)
  125.                 largest = r;
  126.         }
  127.         else
  128.         {
  129.             if(l < heap.size() && heap[l].data < heap[largest].data)
  130.                 largest = l;
  131.  
  132.             if(r < heap.size() && heap[r].data < heap[largest].data)
  133.                 largest = r;
  134.         }
  135.        
  136.         if (largest == i)
  137.             break;
  138.  
  139.         swap(heap[i], heap[largest]);
  140.  
  141.         i = largest;
  142.     }
  143. }
  144.  
  145. sValue extract(vector<sValue> &heap, int &N)
  146. {
  147.     N--;
  148.  
  149.     sValue result = heap[0];
  150.  
  151.     heap[0] = heap[N];
  152.     heap.pop_back();
  153.  
  154.     for (int i = 0; i < 2; i++)
  155.         heapify(heap, 0, i);
  156.  
  157.     return result;
  158. }
  159.  
  160. void insert(vector<sValue> &heap, sValue value, int &N)
  161. {
  162.     int i = N,
  163.         p = parent(i);
  164.  
  165.     heap.push_back(value);
  166.  
  167.  
  168.     for (;p >= 0, i > 0; i = p, p = parent(i))
  169.         if(heap[i].data < heap[p].data)
  170.             swap(heap[i],heap[p]);
  171.  
  172.     N++;
  173. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top