oj.uz

Submission #448357

# Submission time Handle Problem Language Result Execution time Memory
448357 2021-07-29T20:03:00 Z four_specks Balloons (CEOI11_bal) C++17
20 / 100
 237 ms 9948 KB 
#include <bits/stdc++.h>

using namespace std;

double dist(const double &x1, const double &y1, const double &x2)
{
    double dx = (x2 - x1);
    return dx * dx / (4 * y1);
}

void solve()
{
    struct elem
    {
        double x, r;
    };

    int n;
    cin >> n;

    vector<elem> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i].x >> a[i].r;

    vector<double> radii(n);

    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        if (st.empty())
        {
            st.emplace(i);
            radii[i] = a[i].r;
        }
        else
        {
            double sz = a[i].r;
            while (!st.empty())
            {
                int u = st.top();
                sz = min(sz, dist(a[u].x, radii[u], a[i].x));
                if (sz >= a[u].r)
                    st.pop();
                else
                    break;
            }

            st.emplace(i);
            radii[i] = sz;
        }
    }

    cout << fixed << setprecision(3);
    for (int i = 0; i < n; i++)
        cout << radii[i] << '\n';
}

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

    solve();

    return 0;
}

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB 5th numbers differ - expected: '0.1170000000', found: '1.0000000000', error = '0.8830000000'

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 332 KB 148th numbers differ - expected: '8.2380000000', found: '26.0000000000', error = '17.7620000000'

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1140 KB 196th numbers differ - expected: '100.7250000000', found: '111.0000000000', error = '10.2750000000'

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 2712 KB 13947th numbers differ - expected: '0.0810000000', found: '465.1340000000', error = '465.0530000000'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 5240 KB 7239th numbers differ - expected: '0.0590000000', found: '1.0000000000', error = '0.9410000000'

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 6116 KB 4651st numbers differ - expected: '0.4220000000', found: '1.0000000000', error = '0.5780000000'
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 8068 KB 1730th numbers differ - expected: '5.6890000000', found: '6.8060000000', error = '1.1170000000'
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 9948 KB 2718th numbers differ - expected: '2.2100000000', found: '3.0000000000', error = '0.7900000000'
2 Halted 0 ms 0 KB -