Submission #465943

#	Time	Username	Problem	Language	Result	Execution time	Memory
465943		MohamedFaresNebili	Balloons (CEOI11_bal)	C++14	40 / 100	2076 ms	9644 KiB

bal

#include <bits/stdc++.h>
#include "iomanip"

using namespace std;
const long double EPS = 1e-9;

int main()
{
    typedef long double ld;
    int n; cin>>n; vector<pair<ld, ld>>arr(n);
    for(int l=0;l<n;l++) cin>>arr[l].first>>arr[l].second;
    stack<pair<ld, pair<ld, ld>>>s;
    /// S.first -> Radius || S.second.first -> X || S.second.second -> Y
    for(int l=0;l<n;l++) {
        ld lo=0.0, hi=arr[l].second, ans=0.0;
        for(int i=0;i<=50;i++) {
            stack<pair<ld, pair<ld, ld>>>cp=s;
            ld mid=(lo+hi)/2.0; bool can=true;
            while(!cp.empty()) {
                ld r1=cp.top().first, x1=cp.top().second.first, y1=cp.top().second.second;
                ld r2=mid, x2=arr[l].first, y2=mid;
                ld r=fabs(r1-r2), d=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                if(r*r<=d&&d<=(r1+r2)*(r1+r2)) can=false;
                cp.pop();
            }
            if(can) { ans=mid; lo=mid; }
            else { hi=mid; }
        }
        cout<<setprecision(3)<<fixed<<ans<<endl;
        s.push({ans, {arr[l].first, ans}});
    }
}

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