oj.uz

Submission #916365

# Submission time Handle Problem Language Result Execution time Memory
916365 2024-01-25T18:26:30 Z jlass Balloons (CEOI11_bal) C++17
30 / 100
 2000 ms 348 KB 
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD = 1e9 + 7;
ld eps = 1e-12;
/*
Notes for stack:
store dimensions of balloon, as well as for what distance it is significant for
From bottom to top of the stack, the distance it's significant should be increasing 

Find insert size
Because the significant distance is increasing in size, we pop elements in the stack until the distance is less than the insertion distance
Then, take min of balloon size and stack thing

Use Geometries to find balloon sizing and distances ft. Marvin

*/

ld calc_r(ld dx, ld r1) {
    return dx * dx / 4 / r1;
}

//given that r1 > r2, otherwise we do not care
ld calc_x(ld x1, ld r1, ld x2, ld r2) {
    ld l = x2, r = 1e9 + 1;
    while(r - l > eps) {
        ld m = l + (r - l) / 2;
        ld d1 = calc_r(m - x1, r1);
        ld d2 = calc_r(m - x2, r2);
        if(d1 > d2) {
            l = m;
        } else {
            r = m;
        }
    }
    return l + (r - l) / 2;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(3);
    int n; cin >> n;
    stack<pair<ld, pair<ld,ld>>> s; //stored as {significant distance, {x, r}}
    for(int i = 0; i < n; i++) {
        ld x, maxr; cin >> x >> maxr;
        while(s.size() && x > s.top().first) {
            s.pop();
        }
        ld r = min(maxr, s.empty() ? maxr : calc_r(x - s.top().second.first, s.top().second.second));
        //current balloon will always be significant for some portion of graph
        while(s.size() && (r > s.top().second.second || calc_x(s.top().second.first, s.top().second.second, x, r) > s.top().first)) {
            s.pop();
        }
        ld dist = (s.empty() ? 1e9 + 5 : calc_x(s.top().second.first, s.top().second.second, x, r));
        s.push({dist, {x,r}});
        cout << r << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 348 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 2025 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 344 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 2033 ms 344 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 2015 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -