oj.uz

Submission #465943

# Submission time Handle Problem Language Result Execution time Memory
465943 2021-08-17T12:06:02 Z MohamedFaresNebili Balloons (CEOI11_bal) C++14
40 / 100
 2000 ms 9644 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 352 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1829 ms 868 KB 2000 numbers

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 1412 KB Time limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 2832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 5264 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 5956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 7740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 9644 KB Time limit exceeded
2 Halted 0 ms 0 KB -