oj.uz

Submission #1113950

# Submission time Handle Problem Language Result Execution time Memory
1113950 2024-11-17T22:05:35 Z slycelote Mobile (BOI12_mobile) C++17
8 / 100
 591 ms 15944 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);
    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);
        }
    }
    n = x.size();
    double L = 0, R = 4e9;
    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);
            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 << (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 504 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 520 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 2 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 508 KB Output is correct
2 Correct 19 ms 1616 KB Output is correct
3 Incorrect 28 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1616 KB Output is correct
2 Incorrect 38 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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