Advertisement
MKcrazy8

Untitled

Jan 31st, 2023
776
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. struct Drone {
  6.     unsigned int id;
  7.     unsigned int weight;
  8. };
  9.  
  10. void merge(std::vector<Drone> &, unsigned int, unsigned int, unsigned int);
  11.  
  12. void mergeSort(std::vector<Drone> &dr, unsigned int l, unsigned int r) {
  13.     unsigned int mid;
  14.     if (l < r) {
  15.         mid = (l + r) / 2;
  16.         mergeSort(dr, l, mid);
  17.         mergeSort(dr, mid + 1, r);
  18.         merge(dr, l, r, mid);
  19.     }
  20. }
  21.  
  22. void merge(std::vector<Drone> &dr, unsigned int l, unsigned int r, unsigned int mid) {
  23.     unsigned int i_for_left, j_for_right, k;
  24.     std::vector<Drone> cnt(dr.size());
  25.     i_for_left = l;
  26.     k = l;
  27.     j_for_right = mid + 1;
  28.     while (i_for_left <= mid && j_for_right <= r) {
  29.         if (dr[i_for_left].weight < dr[j_for_right].weight) {
  30.             cnt[k] = dr[i_for_left];
  31.             k++;
  32.             i_for_left++;
  33.         } else {
  34.             cnt[k] = dr[j_for_right];
  35.             k++;
  36.             j_for_right++;
  37.         }
  38.     }
  39.     while (i_for_left <= mid) {
  40.         cnt[k] = dr[i_for_left];
  41.         k++;
  42.         i_for_left++;
  43.     }
  44.     while (j_for_right <= r) {
  45.         cnt[k] = dr[j_for_right];
  46.         k++;
  47.         j_for_right++;
  48.     }
  49.     for (i_for_left = l; i_for_left < k; i_for_left++) {
  50.         dr[i_for_left] = cnt[i_for_left];
  51.     }
  52.     cnt.clear();
  53. }
  54.  
  55. int main() {
  56.     std::ios_base::sync_with_stdio(false);
  57.     std::cin.tie(nullptr);
  58.     std::cout.tie(nullptr);
  59.     unsigned int n;
  60.     std::cin >> n;
  61.     std::vector<Drone> drones(n);
  62.     for (int i = 0; i < n; ++i) {
  63.         unsigned int curr_id;
  64.         unsigned int w;
  65.         std::cin >> curr_id >> w;
  66.         drones[i].id = curr_id;
  67.         drones[i].weight = w;
  68.     }
  69.     mergeSort(drones, 0, n - 1);
  70.  
  71.     for (auto i = drones.end() - 1; i >= drones.begin(); --i) {
  72.         std::cout << i->id << "    " << i->weight << std::endl;
  73.     }
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement