# Untitled

Jan 31st, 2023
720
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }