raghuvanshraj

4.cpp

Jul 26th, 2021
787
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  07.03.2020 03:33:09 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. double median(int left, int right, int size) {
  10.     if (size % 2) {
  11.         return left;
  12.     } else {
  13.         return double(left + right) / 2;
  14.     }
  15. }
  16.  
  17. double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
  18.     int n = nums1.size(), m = nums2.size();
  19.     if (n == 0) {
  20.         return (m == 1) ? nums2[0] : median(nums2[(m - 1) / 2], nums2[(m - 1) / 2 + 1], m);
  21.     } else if (m == 0) {
  22.         return (n == 1) ? nums1[0] : median(nums1[(n - 1) / 2], nums1[(n - 1) / 2 + 1], n);
  23.     }
  24.  
  25.     if (n > m) {
  26.         swap(nums1, nums2);
  27.         swap(n, m);
  28.     }
  29.  
  30.     int l = 0, h = n;
  31.     while (l <= h) {
  32.         int i = (l + h) / 2;
  33.         int j = (n + m + 1) / 2 - i;
  34.  
  35.         if (i > 0 and j > 0) {
  36.             int left = max(nums1[i - 1], nums2[j - 1]);
  37.             int right = (i < n) ? min(nums1[i], nums2[j]) : nums2[j];
  38.  
  39.             if (left > right) {
  40.                 if (left == nums1[i - 1]) {
  41.                     h = i;
  42.                 } else {
  43.                     l = i + 1;
  44.                 }
  45.             } else {
  46.                 return median(left, right, n + m);
  47.             }
  48.         } else if (i == 0) {
  49.             int right = (j < m) ? min(nums1[0], nums2[j]) : nums1[0];
  50.             if (nums2[j - 1] > right) {
  51.                 l = i + 1;
  52.             } else {
  53.                 return median(nums2[j - 1], right, n + m);
  54.             }
  55.         } else if (j == 0) {
  56.             if (nums1[i - 1] > nums2[0]) {
  57.                 h = i;
  58.             } else {
  59.                 return median(nums1[i - 1], nums2[0], n + m);
  60.             }
  61.         }
  62.     }
  63.  
  64.     return -1;
  65. }
  66.  
  67.  
  68. int main(int argc, char const *argv[]) {
  69.     int n, m;
  70.     cin >> n >> m;
  71.     vector<int> nums1(n), nums2(m);
  72.  
  73.     for (int i = 0; i < n; ++i) {
  74.         cin >> nums1[i];
  75.     }
  76.  
  77.     for (int i = 0; i < m; ++i) {
  78.         cin >> nums2[i];
  79.     }
  80.  
  81.     double ans = findMedianSortedArrays(nums1, nums2);
  82.     printf("%.1f\n", ans);
  83.  
  84.     return 0;
  85. }
RAW Paste Data