Submission #1285711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285711		thanhliem40	Balloons (CEOI11_bal)	C++20	10 / 100	2097 ms	5100 KiB

bal

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

using namespace std;

// Struct lưu thông tin quả bóng đã bơm (Vị trí, Bán kính)
struct Balloon {
    double X;
    double R;
};

// Hàm tính R_i^max khi tiếp xúc với bóng 'prev' (j)
double calculate_R_max(double X_curr, double M_curr, const Balloon& prev) {
    // Công thức va chạm 2D: R_i = (X_i - X_j)^2 / (4 * R_j)
    // Nếu R_j = 0, thì R_i^max là vô hạn (không bị giới hạn bởi bóng này)
    if (prev.R < 1e-9) { 
        return M_curr; // Giới hạn bởi M_i
    }
    double delta_X = X_curr - prev.X;
    return (delta_X * delta_X) / (4.0 * prev.R);
}

void sol() {
    int n;
    // Đọc N
    if (!(cin >> n)) return;

    // Vector v[i] = {X_i, M_i}
    vector<pair<double, double>> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    vector<double> ans(n);
    // Stack lưu các quả bóng đã bơm tạo thành bao lồi dưới
    stack<Balloon> mono_stack;

    for (int i = 0; i < n; i++) {
        double X_i = v[i].first;
        double M_i = v[i].second;

        // Bán kính cuối cùng R_i ban đầu là M_i
        double R_i = M_i;

        // BƯỚC 1: Tính R_i bằng cách kiểm tra va chạm với các bóng trong Stack
        // (Đây là logic tối ưu O(N) vì chỉ những bóng trên bao lồi mới cần kiểm tra)
        while (!mono_stack.empty()) {
            Balloon t = mono_stack.top();
            
            // Tính bán kính tối đa R_i khi tiếp xúc với bóng t (j)
            double r_max_t = calculate_R_max(X_i, M_i, t);
            
            // R_i bị giới hạn bởi min của tất cả R_max
            R_i = min(R_i, r_max_t);
            
            // Nếu R_i bị giới hạn bởi bóng t (tức là r_max_t < R_i ban đầu)
            // thì ta giữ bóng t và break.
            // Ngược lại, bóng t không giới hạn bóng i.
            // Điều kiện dừng: Bóng t giới hạn bóng i.
            if (r_max_t <= R_i) { 
                break; // Bóng t giới hạn R_i (đã tính R_i = min)
            }
            
            // Nếu r_max_t > R_i: bóng t không phải là giới hạn gần nhất, 
            // ta tiếp tục kiểm tra bóng dưới t.
            // Lưu ý: Nếu không dùng logic bao lồi phức tạp, 
            // ta vẫn phải kiểm tra va chạm với TẤT CẢ các bóng trong Stack
            // và Pop các bóng bị che khuất.
        }

        // BƯỚC 2: Duy trì tính Đơn điệu (Convex Hull)
        // Đây là bước phức tạp nhất, ta cần kiểm tra xem bóng i có che khuất
        // bóng t (đỉnh Stack) đối với các bóng m > i hay không.
        // Dùng một biến thể đơn giản hơn: Pop bóng t nếu nó bị bóng i "che khuất" 
        // cho các bóng tiếp theo (sau khi R_i đã được tính).

        // Để đơn giản, ta chỉ cần kiểm tra xem bóng i có tạo ra một
        // giới hạn nhỏ hơn so với bóng dưới t (nếu có) hay không.
        
        // Cần tính lại R_i_max_t vì vòng lặp trên không pop.
        
        // Vòng lặp chính xác cho Monotonic Stack:
        while (!mono_stack.empty()) {
            Balloon t = mono_stack.top();
            double r_max_t = calculate_R_max(X_i, M_i, t);
            
            // R_i bị giới hạn bởi bóng t
            if (r_max_t < R_i) {
                R_i = r_max_t;
                // Nếu R_i bị giới hạn bởi bóng t, thì bóng t là giới hạn gần nhất, 
                // không cần kiểm tra bóng dưới nó.
                break; 
            }
            // Nếu r_max_t >= R_i (sau khi R_i đã được giới hạn bởi các bóng khác 
            // hoặc M_i): Điều này ngụ ý bóng t không còn là giới hạn cho i. 
            // Ta pop bóng t ra. (Đây là một heuristic đơn giản, không phải logic
            // bao lồi chuẩn nhưng thường hoạt động tốt trong bài này).
            else {
                mono_stack.pop();
            }
        }
        
        // BƯỚC 3: Thêm bóng i vào Stack
        Balloon curr = {X_i, R_i};
        mono_stack.push(curr);
        ans[i] = R_i;
    }

    // In kết quả
    for (auto el : ans) {
        cout << fixed << setprecision(3) << el << '\n'; // In 3 chữ số thập phân và xuống dòng
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("BALLOONS.INP","r",stdin);
    // freopen("BALLOONS.OUT","w",stdout);

    sol();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 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