oj.uz

Submission #1113954

# Submission time Handle Problem Language Result Execution time Memory
1113954 2024-11-17T22:27:02 Z slycelote Mobile (BOI12_mobile) C++17
100 / 100
 774 ms 35400 KB 
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(0); iostream::sync_with_stdio(false);

    int n;
    double d;
    cin >> n >> d;
    vector<double> x, y;
    x.reserve(n); y.reserve(n);
    while (n--) {
        double xx, yy; cin >> xx >> yy;
        yy = fabs(yy);
        if (!x.empty() && x.back() == xx) {
            y.back() = min(y.back(), yy);
        } else {
            x.push_back(xx);
            y.push_back(yy);
        }
    }
    n = x.size();
    double L = 0, R = 4e9;
    while (R - L > 1e-3) {
        double M = (L + R) / 2;
        vector<pair<double, double>> segs;
        for (int i = 0; i < n; ++i) if (M > y[i]) {
            double len = sqrt(M*M - y[i]*y[i]);
            double start = max((double)0.0, x[i] - len), end = min(d, x[i] + len);
            if (start > end) {
                continue;
            }
            while (!segs.empty() && start < segs.back().second) {
                start = min(start, segs.back().first);
                end = max(end, segs.back().second);
                segs.pop_back();
            }
            segs.push_back({start, end});
        }
        if (segs.empty() || segs.size() > 1 || segs.back().first > 0 || segs.back().second < d) {
            L = M;
        } else {
            R = M;
        }
    }

    cout.precision(20);
    cout << (L+R)/2 << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 4 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 4 ms 592 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 3 ms 524 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Output is correct
2 Correct 5 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 2 ms 336 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1352 KB Output is correct
2 Correct 52 ms 2044 KB Output is correct
3 Correct 36 ms 1104 KB Output is correct
4 Correct 37 ms 2384 KB Output is correct
5 Correct 19 ms 472 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1104 KB Output is correct
2 Correct 32 ms 1616 KB Output is correct
3 Correct 39 ms 1360 KB Output is correct
4 Correct 38 ms 2396 KB Output is correct
5 Correct 49 ms 1616 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1616 KB Output is correct
2 Correct 49 ms 2376 KB Output is correct
3 Correct 55 ms 2384 KB Output is correct
4 Correct 45 ms 3656 KB Output is correct
5 Correct 28 ms 1640 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2640 KB Output is correct
2 Correct 52 ms 2120 KB Output is correct
3 Correct 30 ms 592 KB Output is correct
4 Correct 42 ms 3144 KB Output is correct
5 Correct 47 ms 2896 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 1864 KB Output is correct
2 Correct 51 ms 2384 KB Output is correct
3 Correct 32 ms 1360 KB Output is correct
4 Correct 42 ms 1864 KB Output is correct
5 Correct 49 ms 1748 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 8144 KB Output is correct
2 Correct 145 ms 10568 KB Output is correct
3 Correct 144 ms 4600 KB Output is correct
4 Correct 217 ms 8264 KB Output is correct
5 Correct 208 ms 9032 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 11112 KB Output is correct
2 Correct 297 ms 8008 KB Output is correct
3 Correct 163 ms 9032 KB Output is correct
4 Correct 208 ms 8264 KB Output is correct
5 Correct 222 ms 13384 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 9840 KB Output is correct
2 Correct 180 ms 13756 KB Output is correct
3 Correct 159 ms 13116 KB Output is correct
4 Correct 253 ms 21576 KB Output is correct
5 Correct 225 ms 16588 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 4432 KB Output is correct
2 Correct 346 ms 9544 KB Output is correct
3 Correct 164 ms 4432 KB Output is correct
4 Correct 264 ms 15832 KB Output is correct
5 Correct 267 ms 8668 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 16272 KB Output is correct
2 Correct 192 ms 15176 KB Output is correct
3 Correct 189 ms 14664 KB Output is correct
4 Correct 289 ms 24892 KB Output is correct
5 Correct 238 ms 17468 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 4432 KB Output is correct
2 Correct 391 ms 11088 KB Output is correct
3 Correct 209 ms 4432 KB Output is correct
4 Correct 299 ms 11348 KB Output is correct
5 Correct 306 ms 9680 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 12876 KB Output is correct
2 Correct 213 ms 16820 KB Output is correct
3 Correct 214 ms 16064 KB Output is correct
4 Correct 357 ms 28604 KB Output is correct
5 Correct 327 ms 19792 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 4432 KB Output is correct
2 Correct 454 ms 18248 KB Output is correct
3 Correct 241 ms 4432 KB Output is correct
4 Correct 341 ms 12872 KB Output is correct
5 Correct 362 ms 18748 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 20808 KB Output is correct
2 Correct 296 ms 20028 KB Output is correct
3 Correct 266 ms 19016 KB Output is correct
4 Correct 412 ms 35184 KB Output is correct
5 Correct 361 ms 22200 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 4432 KB Output is correct
2 Correct 560 ms 25900 KB Output is correct
3 Correct 298 ms 16828 KB Output is correct
4 Correct 431 ms 35400 KB Output is correct
5 Correct 440 ms 28220 KB Output is correct