oj.uz

Submission #1093060

# Submission time Handle Problem Language Result Execution time Memory
1093060 2024-09-25T19:00:07 Z TommasoUlian Mobile (BOI12_mobile) C++17
0 / 100
 720 ms 45836 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<pair<double, double>> torri;
ll n, L;

bool good(double r) {
    queue<pair<double, double>> s;
    
    for (auto a : torri) {
        double x = a.first, y = a.second;
        if (abs(y) <= r - 1e-6) { // Ensure we're within the valid range
            double dx = sqrt((r + y) * (r - y));
            s.push({x - dx, x + dx});
        }
    }

    double curr = 0;
    while (!s.empty()) {
        if (curr >= L) return true; // Early exit if covered
        auto seg = s.front();
        s.pop();
        if (seg.first <= curr) {
            curr = max(seg.second, curr);
        } else {
            return false; // Can't cover this gap
        }
    }
    
    return curr >= L; // Final check
}

void solve() {
    cin >> n >> L;
    torri.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> torri[i].first >> torri[i].second;
    }

    double l = 1, r = 2e9; // Set realistic bounds
    double ans = r;

    while (r - l > 1e-4) { // Tighter precision for convergence
        double c = (r + l) / 2;
        if (good(c)) {
            ans = c;
            r = c;
        } else {
            l = c;
        }
    }

    cout << setprecision(18) << (l + r) / 2 << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    return 0;
}

Compilation message

mobile.cpp: In function 'void solve()':
mobile.cpp:42:12: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   42 |     double ans = r;
      |            ^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 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 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3948 KB Output is correct
2 Incorrect 57 ms 4396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5272 KB Output is correct
2 Incorrect 71 ms 5184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 20148 KB Output is correct
2 Correct 361 ms 22784 KB Output is correct
3 Correct 315 ms 22404 KB Output is correct
4 Incorrect 206 ms 23920 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 23028 KB Output is correct
2 Incorrect 353 ms 21952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 24108 KB Output is correct
2 Incorrect 415 ms 27028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 27612 KB Output is correct
2 Incorrect 420 ms 26104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 27864 KB Output is correct
2 Incorrect 449 ms 31512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 31940 KB Output is correct
2 Incorrect 463 ms 30148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 31944 KB Output is correct
2 Incorrect 550 ms 35760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 36516 KB Output is correct
2 Incorrect 566 ms 34380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 39528 KB Output is correct
2 Incorrect 709 ms 44516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 45440 KB Output is correct
2 Incorrect 643 ms 45836 KB Output isn't correct
3 Halted 0 ms 0 KB -