Submission #1217505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217505		henrii	Balloons (CEOI11_bal)	C++17	0 / 100	103 ms	6680 KiB

bal

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define pii pair<int, int>
#define ll long long

struct Balloon
{
    long double x, r;
};

int main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    int n;
    cin >> n;

    vector<Balloon> balloon(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> balloon[i].x >> balloon[i].r;
    }

    auto maxRadius = [&](int idx1, int idx2) -> long double
    {
        return (balloon[idx1].x - balloon[idx2].x) * (balloon[idx1].x - balloon[idx2].x) / (4.0 * balloon[idx1].r);
    };

    stack<pii> s;
    s.push({balloon[0].r, 0});
    for (int i = 1; i < n; ++i)
    {
        while (!s.empty() && maxRadius(s.top().second, i) > s.top().first)
            s.pop();

        balloon[i].r = min(balloon[i].r, maxRadius(s.top().second, i));
        s.push({balloon[i].r, i});
    }

    cout << setprecision(4);
    for (int i = 0; i < n; ++i)
    {
        cout << balloon[i].r << endl;
    }


    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10