oj.uz

Submission #768929

# Submission time Handle Problem Language Result Execution time Memory
768929 2023-06-28T22:10:05 Z orcslop Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 48100 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 1e6; 

int n; 
double l; 
pair<double, double> v[MAXN]; 

bool check(double rad){
    vector<pair<double, double>> intervals; 
    for(int i = 0; i < n; i++){
        if(v[i].second >= rad) continue; 
        pair<double, double> add; 
        add.first = min(l, max(v[i].first - sqrt(rad * rad - v[i].second * v[i].second), (double)0)); 
        add.second = max((double)0, min(v[i].first  + sqrt(rad * rad - v[i].second * v[i].second), l)); 
        intervals.push_back(add); 
    }
    sort(intervals.begin(), intervals.end()); 
    if(intervals.empty() || intervals[0].first != 0 || intervals.back().second != l) return false; 
    double curr = intervals[0].second; 
    for(auto x : intervals) {
        if(x.first > curr) return false; 
        else curr = x.second; 
    }
    return true; 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> l; 
    for(int i = 0; i < n; i++){
        cin >> v[i].first >> v[i].second; 
    }
    // cout << check(5.55); 
    double low = 0, high = (double) 1e8; 
    while (low + 0.0000001 < high) {
        double mid = low + (high - low) / 2;
        if (check(mid)) high = mid;
        else low = mid;
    }
    cout << setprecision(15) << low << '\n'; 
    return 0; 
}

Subtask #1
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 620 KB Output is correct
2 Correct 9 ms 612 KB Output is correct
3 Correct 15 ms 616 KB Output is correct
4 Incorrect 18 ms 700 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 5224 KB Output is correct
2 Correct 270 ms 5008 KB Output is correct
3 Correct 355 ms 5064 KB Output is correct
4 Incorrect 336 ms 7100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 5520 KB Output is correct
2 Correct 352 ms 5540 KB Output is correct
3 Correct 438 ms 5544 KB Output is correct
4 Incorrect 358 ms 7156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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