oj.uz

Submission #1113952

# Submission time Handle Problem Language Result Execution time Memory
1113952 2024-11-17T22:22:59 Z slycelote Mobile (BOI12_mobile) C++17
75 / 100
 1000 ms 44356 KB 
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

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

    int n;
    long double d;
    cin >> n >> d;
    vector<long double> x, y;
    x.reserve(n); y.reserve(n);
    while (n--) {
        long 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();
    long double L = 0, R = 4e9;
    while (R - L > 1e-4) {
        long double M = (L + R) / 2;
        vector<pair<long double, long double>> segs;
        for (int i = 0; i < n; ++i) if (M > y[i]) {
            long double len = sqrt(M*M - y[i]*y[i]);
            long double start = max((long 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 6 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2384 KB Output is correct
2 Correct 89 ms 2128 KB Output is correct
3 Correct 66 ms 2640 KB Output is correct
4 Correct 54 ms 4176 KB Output is correct
5 Correct 13 ms 848 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 592 KB Output is correct
2 Correct 40 ms 1360 KB Output is correct
3 Correct 57 ms 2524 KB Output is correct
4 Correct 59 ms 3912 KB Output is correct
5 Correct 60 ms 4432 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 3144 KB Output is correct
2 Correct 80 ms 2092 KB Output is correct
3 Correct 109 ms 3556 KB Output is correct
4 Correct 62 ms 5448 KB Output is correct
5 Correct 39 ms 2128 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 1736 KB Output is correct
2 Correct 73 ms 3032 KB Output is correct
3 Correct 40 ms 1736 KB Output is correct
4 Correct 62 ms 5448 KB Output is correct
5 Correct 71 ms 4256 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3420 KB Output is correct
2 Correct 72 ms 3016 KB Output is correct
3 Correct 38 ms 1864 KB Output is correct
4 Correct 60 ms 5532 KB Output is correct
5 Correct 68 ms 4180 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 15944 KB Output is correct
2 Correct 154 ms 12104 KB Output is correct
3 Correct 167 ms 11716 KB Output is correct
4 Correct 334 ms 25672 KB Output is correct
5 Correct 371 ms 19528 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 4432 KB Output is correct
2 Correct 702 ms 22468 KB Output is correct
3 Correct 283 ms 10056 KB Output is correct
4 Correct 351 ms 25416 KB Output is correct
5 Correct 419 ms 21844 KB Output is correct

Subtask #14
0 / 5.0

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

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4432 KB Output is correct
2 Correct 717 ms 27060 KB Output is correct
3 Correct 248 ms 11336 KB Output is correct
4 Correct 390 ms 30800 KB Output is correct
5 Correct 497 ms 25672 KB Output is correct

Subtask #16
0 / 5.0

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

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 4432 KB Output is correct
2 Correct 833 ms 31168 KB Output is correct
3 Correct 351 ms 12932 KB Output is correct
4 Correct 479 ms 35524 KB Output is correct
5 Correct 555 ms 31048 KB Output is correct

Subtask #18
0 / 5.0

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

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 4564 KB Output is correct
2 Correct 907 ms 35656 KB Output is correct
3 Correct 378 ms 14072 KB Output is correct
4 Correct 550 ms 40936 KB Output is correct
5 Correct 609 ms 36652 KB Output is correct

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 4432 KB Output is correct
2 Execution timed out 1083 ms 44356 KB Time limit exceeded
3 Halted 0 ms 0 KB -