oj.uz

Submission #1101158

# Submission time Handle Problem Language Result Execution time Memory
1101158 2024-10-15T17:02:25 Z BLOBVISGOD Mobile (BOI12_mobile) C++17
50 / 100
 1000 ms 64712 KB 
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,l; cin >> n >> l;
    vector<array<ll,2>> a(n);
    rep(i,0,n) rep(j,0,2) cin >> a[i][j];
    rep(i,0,n) a[i][1] = a[i][1]*a[i][1];

    double lo = 0, hi = 2e9;
    rep(iter,0,72){
        double mid = (lo+hi)/2, mid2 = mid*mid;
        vector<array<double,2>> segs;
        rep(i,0,n) if (a[i][1] < mid2){
            double d = sqrt(mid2 - a[i][1]);
            segs.push_back({a[i][0]-d,a[i][0]+d});
        }
        sort(all(segs), [&](auto l, auto r){
            return l[1] < r[1];
        });
        double r = 0;
        for(auto [L,R] : segs){
            if (L <= r) r = max(r,R);
        }
        if (r < l) lo = mid;
        else hi = mid;
    }
    cout << setprecision(15) << lo << '\n';
}

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 6 ms 592 KB Output is correct
2 Correct 10 ms 636 KB Output is correct
3 Correct 4 ms 508 KB Output is correct
4 Correct 9 ms 592 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 792 KB Output is correct
2 Correct 24 ms 816 KB Output is correct
3 Correct 16 ms 784 KB Output is correct
4 Correct 7 ms 816 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 784 KB Output is correct
2 Correct 24 ms 988 KB Output is correct
3 Correct 21 ms 784 KB Output is correct
4 Correct 7 ms 800 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 800 KB Output is correct
2 Correct 24 ms 800 KB Output is correct
3 Correct 16 ms 864 KB Output is correct
4 Correct 7 ms 800 KB Output is correct
5 Correct 10 ms 800 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 5688 KB Output is correct
2 Correct 564 ms 6024 KB Output is correct
3 Correct 264 ms 3800 KB Output is correct
4 Correct 111 ms 6060 KB Output is correct
5 Correct 122 ms 3468 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 5948 KB Output is correct
2 Correct 159 ms 5580 KB Output is correct
3 Correct 157 ms 6088 KB Output is correct
4 Correct 119 ms 6204 KB Output is correct
5 Correct 106 ms 6648 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 5980 KB Output is correct
2 Correct 663 ms 6288 KB Output is correct
3 Correct 317 ms 6156 KB Output is correct
4 Correct 74 ms 7472 KB Output is correct
5 Correct 198 ms 6124 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 7236 KB Output is correct
2 Correct 712 ms 7652 KB Output is correct
3 Correct 506 ms 6680 KB Output is correct
4 Correct 75 ms 7524 KB Output is correct
5 Correct 182 ms 6920 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 7192 KB Output is correct
2 Correct 770 ms 7076 KB Output is correct
3 Correct 489 ms 6712 KB Output is correct
4 Correct 77 ms 7504 KB Output is correct
5 Correct 177 ms 6940 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 28624 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 1041 ms 32532 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 1052 ms 41940 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 1054 ms 47008 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 1032 ms 45624 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 1062 ms 50416 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 1044 ms 49344 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 1049 ms 56552 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 1062 ms 57540 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 1044 ms 64712 KB Time limit exceeded
2 Halted 0 ms 0 KB -