Submission #1266636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266636		ngunguoi45	Balloons (CEOI11_bal)	C++20	100 / 100	107 ms	6488 KiB

bal

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+5;

int n;
double x[maxn], r[maxn];

double dist (int i, int j, double p) {
    return 1.0  * (x[i]-x[j]) * (x[i]-x[j]) / (4.0*p);
}

void read_and_prep() {
    cin >> n;
    for (int i = 1;i <= n; i++) {
        cin >> x[i] >> r[i];
    }
}

namespace sub1 {
    // init
    double ans[maxn];
    // func
    bool check () {
        return (n <= 2000);
    }
    void solve () {
        ans[1] = r[1];
        for (int i = 2;i <= n; i++) {
            double radius = r[i];
            for (int j = 1;j < i; j++) {
                radius = min (radius, dist(j, i, ans[j]));
            }
            ans[i] = radius;
        }
        for (int i = 1;i <= n; i++) cout << fixed << setprecision(3) << ans[i] << "\n";
        cout << "\n";
    }
}

namespace sub2 {
    // init
    double ans[maxn];
    stack<int> st;
    // func
    void solve () {
        st.push(1);
        ans[1] = r[1];
        for (int i = 2;i <= n; i++) {
            double radius = r[i];
            while ((int)st.size()) {
                int j = (int)st.top();
                radius = min (radius, dist(j,i,ans[j]));
                if (radius >= ans[j]) st.pop();
                else break;
            }
            ans[i] = radius;
            st.push(i);
        }
        for  (int i = 1;i <= n; i++) cout << fixed << setprecision(3) << ans[i] << "\n";
        cout << "\n";
    }
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    read_and_prep();

    if (sub1::check()) sub1::solve();
    else sub2::solve();
    return 0;
}

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