oj.uz

Submission #951142

# Submission time Handle Problem Language Result Execution time Memory
951142 2024-03-21T08:36:06 Z Kavelmydex Mobile (BOI12_mobile) C++17
0 / 100
 492 ms 49068 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define vi vector<int>
#define rep(i,x,n) for(int i=x; i<n; ++i)
#define For(i,n) rep(i,0,n)
#define endl "\n"
#define sp ' '
#define pb push_back
#define f first
#define s second
#define sz size()
#define all(x) (x).begin(),(x).end()
 
const int N = 2e5+1, OO = 1e18, mod = 1e9;
void tr(int a, int b){cout << a << sp << b << endl;}
void cmx(double &a, double b){a = max(a,b);}
void cmn(double &a, double b){a = min(a,b);}

pi p[N];
deque <pi> v, u;
int n,l; 
int fun(int j){
    if(u.sz == 1) return j ? -OO: OO;
    int X = abs(u[0].f - u[1].f);
    int d = ( u[0].s * u[0].s - u[1].s * u[1].s + X * X ) / (-2*X);
    return d;
}
void deb(){
    deque <pi> t;
    For(i,n){
        int j = i, mn = OO;
        while(j < n && v[i].f == v[j].f) mn = min(mn, v[j].s), j++;
        t.pb(v[i]);
        i = j-1;
    }
    v = t; n = v.sz;
}
int32_t main() {
    // ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    For(i,n){
        int x,y; cin >> x >> y;
        y = abs(y);
        v.pb({x,y});
    }
    deb();
    int bst = OO;
    For(i,n){
        auto [x,y] = v[i];
        while(u.sz > 1 && bst + u.front().f < x){
            u.pop_front(); 
            while(bst = fun(0) < 0) u.pop_front();
        }
        while(u.sz && u.back().s * u.back().s >= (abs(x-u.back().f)*abs(x-u.back().f) + y*y)) u.pop_back();
        if(u.sz && abs(u.front().f-x) * abs(u.front().f-x) + u.front().s * u.front().s <= y*y){
            u.pb(v[i]);
        } else {
            u.clear(); 
            u.pb(v[i]);
        }
        p[i] = u.front();
    }
    double mn1 = OO, mn2 = OO, ans = 0;
    for(auto [x,y]: v){
        cmn(mn1, x*x+y*y);
        cmn(mn2, abs(x-l)*abs(x-l)+y*y);
    }
    cmx(ans, max(mn1,mn2));
    bst = -OO;
    for(int i=n-1; i>=1; --i){
        auto [x,y] = v[i];
        while(u.sz > 1 && -bst + u.front().f > x){
            u.pop_front(); 
            while(bst = fun(1) > 0) u.pop_front();
        }
        while(u.sz && u.back().s * u.back().s >= (abs(x-u.back().f)*abs(x-u.back().f) + y*y)) u.pop_back();
        if(u.sz && abs(u.front().f-x) * abs(u.front().f-x) + u.front().s * u.front().s <= y*y){
            u.pb(v[i]);
        }else {
            u.clear(); 
            u.pb(v[i]);
        }
        pi L = p[i-1], R = u.front();
        double X = abs(R.f - L.f);
        double d = ( R.s * R.s - L.s * L.s + X*X ) / (2*X);
        if(R.f >= 0 && L.f >= 0){
            cmx(ans, sqrt(d*d + L.s*L.s));           
        }
        if(R.f > l && L.f <= l){
            cmx(ans, min(mn2,sqrt(d*d + L.s * L.s)));
        }
        if(L.f < 0 && R.f >= 0){
            cmx(ans, min(mn2,sqrt(d*d + L.s * L.s)));
        }
    }
    cout << fixed << setprecision(4) << ans << endl;
    return 0;
}

Compilation message

mobile.cpp: In function 'int32_t main()':
mobile.cpp:54:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   54 |             while(bst = fun(0) < 0) u.pop_front();
      |                   ~~~~^~~~~~~~~~~~
mobile.cpp:76:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   76 |             while(bst = fun(1) > 0) u.pop_front();
      |                   ~~~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 27956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 32216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 36368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 299 ms 40732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 386 ms 49068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

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