Submission #1159979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159979		jared	Balloons (CEOI11_bal)	C++20	100 / 100	230 ms	6516 KiB

bal

#include "bits/stdc++.h"
#define int long long
#define double long double
using namespace std;

int n;
vector<int> d;
vector<double> r;

signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> n;
    d.resize(n);
    r.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> r[i];
    }

    //           (r_1 + r_2)^2 = (d_2 - d_1)^2 + (r_1 - r_2)^2
    // r_1^2 + 2r_1r_2 + r_2^2 = (d_2 - d_1)^2 + r_1^2 - 2r_1r_2 + r_2^2
    //                4r_1_r_2 = (d_2 - d_1)^2
    //                     r_2 = (d_2 - d_1)^2 / 4r_1

    // Consider balloon a and b (a < b), if r_a <= r_b,
    // balloon b blocks balloon a completely, when there is a new balloon after b
    // we do not have to check balloon a
    stack<int> mono;
    for (int i = 0; i < n; i++) {
        double size = r[i];

        while (!mono.empty()) {
            int j = mono.top();
            size = min(size, (d[i] - d[j]) * (d[i] - d[j]) / 4.l / r[j]);

            if (size >= r[j]) // balloon j does not 'block' balloon i completely, need to check larger balloon before j
                mono.pop();
            else break;
        }
        mono.push(i);

        r[i] = size;
        cout << fixed << setprecision(3) << size << endl;
    }
    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