Median-D&C

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

pair<int, int> get_mid_members_of_even_length_array(const vector<int>& arr, int l, int h) {
    return make_pair(arr[(l + h) / 2], arr[(l + h) / 2 + 1]);
}

double get_median_of_sorted_array(const vector<int>& arr, int l, int h) {
    int size = h - l + 1;

    if (size % 2 == 0) {
        pair<int, int> mid_members = get_mid_members_of_even_length_array(arr, l, h);
        return (mid_members.first + mid_members.second) / 2.0;
    } else {
        return arr[(l + h) / 2];
    }
}

double find_median_of_sorted_arrays(const vector<int>& arr1, const vector<int>& arr2, int l1, int h1, int l2, int h2) {
    int size = h1 - l1 + 1;

    if (size == 0) {
        return 0;
    }

    if (size == 1) {
        return (arr1[l1] + arr2[l2]) / 2.0;
    }

    if (size == 2) {
        return (max(arr1[l1], arr2[l2]) + min(arr1[h1], arr2[h2])) / 2.0;
    }

    if (size % 2 == 0) {
        pair<int, int> mid_arr1 = get_mid_members_of_even_length_array(arr1, l1, h1);
        pair<int, int> mid_arr2 = get_mid_members_of_even_length_array(arr2, l2, h2);

        if (mid_arr1.first >= mid_arr2.first && mid_arr1.second <= mid_arr2.second) {
            return get_median_of_sorted_array(arr1, l1, h1);
        }

        if (mid_arr1.first <= mid_arr2.first && mid_arr1.second >= mid_arr2.second) {
            return get_median_of_sorted_array(arr2, l2, h2);
        }
    }

    double med_arr1 = get_median_of_sorted_array(arr1, l1, h1);
    double med_arr2 = get_median_of_sorted_array(arr2, l2, h2);

    if (med_arr1 == med_arr2) {
        return med_arr1;
    }

    if (med_arr1 < med_arr2) {
        return find_median_of_sorted_arrays(arr1, arr2, ceil((l1 + h1) / 2.0), h1, l2, (l2 + h2) / 2);
    }

    return find_median_of_sorted_arrays(arr1, arr2, l1, (l1 + h1) / 2, ceil((l2 + h2) / 2.0), h2);
}

int main() {
    int n;
    cin >> n;

    vector<int> arr1(n);
    vector<int> arr2(n);

    for (int i = 0; i < n; i++) {
        cin >> arr1[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> arr2[i];
    }

    double ans = find_median_of_sorted_arrays(arr1, arr2, 0, n - 1, 0, n - 1);
    int intPart = static_cast<int>(ans);
    int floatPart = static_cast<int>((ans - intPart) * 10);

    cout << intPart << "." << floatPart << endl;

    return 0;
}