Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.0 kB
2
Indexable
Never
#include <iostream>
#include <vector>
using namespace std;

typedef long double ld;

int main() {
    cout.precision(20);
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> pref_min(n), pref_max(n), suff_min(n), suff_max(n);
    for (int& i : arr) cin >> i;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            pref_min[i] = arr[i];
            pref_max[i] = arr[i];
        }
        else {
            pref_min[i] = min(pref_min[i - 1], arr[i]);
            pref_max[i] = max(pref_max[i - 1], arr[i]);
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i == n - 1) {
            suff_min[i] = arr[i];
            suff_max[i] = arr[i];
        }
        else {
            suff_min[i] = min(arr[i], suff_min[i + 1]);
            suff_max[i] = max(arr[i], suff_max[i + 1]);
        }
    }

    vector<pair<ld, ld>> answer(n + 1, { 1e18, 0 });
    for (int k = 1; k <= n; k++) {
        if (k == n) {
            answer[k] = { 0, 1 };
        }
        else {
            ld pmin = pref_min[n - k - 1];
            ld pmax = pref_max[n - k - 1];
            ld smin = suff_min[n - k];
            ld smax = suff_max[n - k];

            // first case pmax and pmin
            ld left_border = max(ld(0), 1.0 - pmax / smax);
            ld right_border = 1.0 - pmin / smin;

            if (left_border <= right_border) {
                if (pmax - pmin <= answer[k].first) {
                    answer[k].first = pmax - pmin;
                    answer[k].second = right_border;
                }
            }

            // second case pmax and smin
            left_border = max(1.0 - pmin / smin, 1.0 - pmax / smax);
            left_border = max(ld(0), left_border);

            if (left_border <= 1) {
                if (pmax - smin * left_border <= answer[k].first) {
                    answer[k].first = pmax - smin * left_border;
                    answer[k].second = left_border;
                }
            }

            // third case smax and pmin
            right_border = min(1 - pmax / smax, 1 - pmin / smin);
            if (right_border >= 0) {
                if (smax * (1.0 - right_border) - pmin <= answer[k].first) {
                    answer[k].first = smax * (1.0 - right_border) - pmin;
                    answer[k].second = right_border;
                }
            }

            // fourth case smax and smin
            right_border = 1 - pmax / smax;
            left_border = max(ld(0), 1 - pmin / smin);
            if (left_border <= right_border) {
                if (smax * (1 - right_border) - smin * (1 - right_border) <= answer[k].first) {
                    answer[k].first = smax * (1 - right_border) - smin * (1 - right_border);
                    answer[k].second = right_border;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << answer[n - i + 1].second << ' ';
    }
    cout << '\n';
}