oj.uz

Submission #1113949

# Submission time Handle Problem Language Result Execution time Memory
1113949 2024-11-17T22:00:42 Z slycelote Mobile (BOI12_mobile) C++17
0 / 100
 558 ms 24796 KB 
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

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

    int n, d; cin >> n >> d;
    vector<double> x, y;
    x.reserve(n); y.reserve(n);
    double R = 2e9, L1 = R, L2 = R;
    while (n--) {
        int xx, yy; cin >> xx >> yy;
        yy = abs(yy);
        if (!x.empty() && x.back() == xx) {
            y.back() = min(y.back(), (double)yy);
        } else {
            x.push_back(xx);
            y.push_back(yy);
        }
        auto d1 = hypot(xx, (double)yy);
        auto d2 = hypot(d-xx, (double)yy);
        R = min(R, max(d1, d2));
        L1 = min(L1, d1);
        L2 = min(L1, d2);
    }
    double L = max(L1, L2);
    n = x.size();
    while (R > L + 1e-3) {
        double M = L + (R-L)/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(0.0, x[i] - len), end = min((double)d, x[i] + len);
            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 << (L+R)/2 << endl;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 3108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2384 KB Output is correct
2 Incorrect 14 ms 2436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 2684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 4560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 289 ms 12348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 12600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 15012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 14408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 404 ms 17216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 15932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 442 ms 19768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 17464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 558 ms 24796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 21048 KB Output isn't correct
2 Halted 0 ms 0 KB -