Nik_Perepelov

12 контест

Dec 1st, 2021 (edited)
472
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // 1
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. vector<int> v;
  9.  
  10. void make_piramyde(int root, int b) {
  11.     int child;
  12.     while (root * 2 <= b) {
  13.         if (root * 2 == b || v[root * 2 + 1] < v[root * 2])
  14.             child = root * 2;
  15.         else
  16.             child = root * 2 + 1;
  17.         if (v[root] < v[child]) {
  18.             swap(v[root], v[child]);
  19.             root = child;
  20.         } else
  21.             break;
  22.     }
  23. }
  24.  
  25. int main() {
  26.     cin >> n;
  27.     v.resize(n);
  28.     for (int i = 0; i < n; i++)
  29.         cin >> v[i];
  30.  
  31.     for (int i = n / 2; i >= 0; i--)
  32.         make_piramyde(i, n - 1);
  33.     for (int i = n - 1; i >= 1; i--) {
  34.         swap(v[0], v[i]);
  35.         make_piramyde(0, i - 1);
  36.     }
  37.  
  38.     for (int i = 0; i < n; i++)
  39.         cout << v[i] << ' ';
  40.  
  41.  
  42. }
  43.  
  44. //2
  45.  
  46. #include <iostream>
  47. #include <vector>
  48.  
  49. using namespace std;
  50.  
  51. int n;
  52. vector<int> heap;
  53. int t, command;
  54.  
  55. void heapify(int i) {
  56.     int l = 2 * i + 1, r = 2 * i + 2;
  57.  
  58.     if (r < n && heap[i] < heap[r]) {
  59.         swap(heap[i], heap[r]);
  60.         heapify(r);
  61.  
  62.     }
  63.     if (l < n && heap[i] < heap[l]) {
  64.         swap(heap[i], heap[l]);
  65.         heapify(l);
  66.     }
  67. }
  68.  
  69.  
  70. int main() {
  71.     cin >> t;
  72.  
  73.     heap.resize(1000000);
  74.      n = 0;
  75.  
  76.     for (int i = 0; i < t; i++) {
  77.         cin >> command;
  78.         if (command == 0) {
  79.             int value, current = n, pred = (n - 1) / 2;
  80.             cin >> value;
  81.             heap[current] = value;
  82.             while (pred >= 0 && current > 0) {
  83.                 if (heap[current] > heap[pred])
  84.                     swap(heap[current], heap[pred]);
  85.                 current = pred;
  86.                 pred = (current - 1) / 2;
  87.             }
  88.             n++;
  89.         } else {
  90.             cout << heap[0] << endl;
  91.             n--;
  92.             heap[0] = heap[n];
  93.             heapify(0);
  94.         }
  95.     }
  96.  
  97. }
RAW Paste Data