oj.uz

Submission #714924

# Submission time Handle Problem Language Result Execution time Memory
714924 2023-03-25T13:24:47 Z MilosMilutinovic Balloons (CEOI11_bal) C++14
100 / 100
 1080 ms 8140 KB 
#include <bits/stdc++.h>

using i64 = long long;

const double eps = 1E-8;

double solve(double x1, double r, double x2) {
    double low = 0, high = 1.01E9, R = 0;
   for (int i = 0; i < 100; i++) {
        double mid = (low + high) / 2;
        double dist = std::sqrt((long double) (x1 - x2) * (x1 - x2) + (long double) (r - mid) * (r - mid));
        if (dist >= r + mid) {
            R = mid;
            low = mid;
        } else {
            high = mid;
        }
    }
    return R;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<double> x(n), r(n);
    for (int i = 0; i < n; i++) {
        std::cin >> x[i] >> r[i];
    }

    std::vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty()) {
            int j = stk.back();
            double nr = solve(x[j], r[j], x[i]);
            r[i] = std::min(r[i], nr);
            if (r[i] >= r[j]) {
                stk.pop_back();
            } else {
                break;
            }
        }
        stk.push_back(i);
        std::cout << std::fixed << std::setprecision(5) << r[i] << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 356 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 824 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 1692 KB 50000 numbers
2 Correct 258 ms 1516 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 2992 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 3468 KB 115362 numbers
2 Correct 637 ms 5516 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 4400 KB 154271 numbers
2 Correct 1080 ms 4980 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1073 ms 5452 KB 200000 numbers
2 Correct 1059 ms 8140 KB 199945 numbers