Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- struct Drone {
- unsigned int id;
- unsigned int weight;
- };
- void merge(std::vector<Drone> &, unsigned int, unsigned int, unsigned int);
- void mergeSort(std::vector<Drone> &dr, unsigned int l, unsigned int r) {
- unsigned int mid;
- if (l < r) {
- mid = (l + r) / 2;
- mergeSort(dr, l, mid);
- mergeSort(dr, mid + 1, r);
- merge(dr, l, r, mid);
- }
- }
- void merge(std::vector<Drone> &dr, unsigned int l, unsigned int r, unsigned int mid) {
- unsigned int i_for_left, j_for_right, k;
- std::vector<Drone> cnt(dr.size());
- i_for_left = l;
- k = l;
- j_for_right = mid + 1;
- while (i_for_left <= mid && j_for_right <= r) {
- if (dr[i_for_left].weight < dr[j_for_right].weight) {
- cnt[k] = dr[i_for_left];
- k++;
- i_for_left++;
- } else {
- cnt[k] = dr[j_for_right];
- k++;
- j_for_right++;
- }
- }
- while (i_for_left <= mid) {
- cnt[k] = dr[i_for_left];
- k++;
- i_for_left++;
- }
- while (j_for_right <= r) {
- cnt[k] = dr[j_for_right];
- k++;
- j_for_right++;
- }
- for (i_for_left = l; i_for_left < k; i_for_left++) {
- dr[i_for_left] = cnt[i_for_left];
- }
- cnt.clear();
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- std::cout.tie(nullptr);
- unsigned int n;
- std::cin >> n;
- std::vector<Drone> drones(n);
- for (int i = 0; i < n; ++i) {
- unsigned int curr_id;
- unsigned int w;
- std::cin >> curr_id >> w;
- drones[i].id = curr_id;
- drones[i].weight = w;
- }
- mergeSort(drones, 0, n - 1);
- for (auto i = drones.end() - 1; i >= drones.begin(); --i) {
- std::cout << i->id << " " << i->weight << std::endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement