oj.uz

Submission #684203

# Submission time Handle Problem Language Result Execution time Memory
684203 2023-01-20T16:14:59 Z Brownbear2710 Mobile (BOI12_mobile) C++14
0 / 100
 1000 ms 93724 KB 
/*
    So, which of the favours
    of your Lord would you deny?
*/

#include <bits/stdc++.h>

#ifdef ADIB_PC
#include "dbg.h"
#else
#define dbg(...)
#endif

using namespace std;
using ll = long long;
using ld = long double;

#define fast_IO ios_base::sync_with_stdio(0), cin.tie(NULL);
#define show(x) cout << #x << ": " << x << endl;
#define all(x) x.begin(), x.end()
#define MAXN 200005

struct point
{
    ld x, y;
    point(){}
    point(ld _x, ld _y) : x(_x), y(_y) {}
    bool operator<(point &p) const
    {
        if(x != p.x) x < p.x;
        return y < p.y;
    }
};

vector<point> pts;
ld l;

bool can_cover(ld d)
{
    vector<pair<ld,ld>> seg;
    for(int i = 0; i < pts.size(); i++)
    {
        auto [x, y] = pts[i];
        if(d < y) continue;
        ld dx = sqrt(d*d-y*y);
        ld left = max((ld)0, x - dx), right = min(x + dx, l);
        seg.emplace_back(left, right);
    }
    
    double lf = 0;
    for(int i = 0; i < seg.size(); i++)
    {
        if(seg[i].first > l or seg[i].second < 0) continue;
        if(seg[i].first <= lf) lf = seg[i].second;
    }
    return lf >= l;
}

int main()
{
    fast_IO;
    int T = 1;
    // cin >> T;
    while(T--)
    {
        int n;
        cin >> n >> l;
        for(int i = 0 ; i < n; i++)
        {
            point p;
            cin >> p.x >> p.y;
            p.x = abs(p.x), p.y = abs(p.y);
            if(pts.size() == 0 || pts.back().x != p.x)
                pts.push_back(p);
        }
        ld ans = 1e15, lo  = 0, hi = 1e10;
        while(abs(lo-hi) >= 0.000001)
        {
            ld mid = (lo + hi)/2;
            if(can_cover(mid))
            {
                ans = mid;
                hi = mid;
            }
            else lo = mid;
        }
        cout << fixed << setprecision(6) << ans << "\n";
    }
    return 0;
}

Compilation message

mobile.cpp: In member function 'bool point::operator<(point&) const':
mobile.cpp:30:24: warning: statement has no effect [-Wunused-value]
   30 |         if(x != p.x) x < p.x;
      |                      ~~^~~~~
mobile.cpp: In function 'bool can_cover(ld)':
mobile.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < pts.size(); i++)
      |                    ~~^~~~~~~~~~~~
mobile.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         auto [x, y] = pts[i];
      |              ^
mobile.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < seg.size(); i++)
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 908 KB Output is correct
2 Correct 15 ms 992 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 8 ms 1020 KB Output is correct
5 Incorrect 3 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 10088 KB Output is correct
2 Correct 182 ms 6868 KB Output is correct
3 Correct 165 ms 10152 KB Output is correct
4 Incorrect 107 ms 12628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 5184 KB Output is correct
2 Correct 158 ms 6556 KB Output is correct
3 Correct 74 ms 2816 KB Output is correct
4 Incorrect 121 ms 12736 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 10872 KB Output is correct
2 Correct 159 ms 5188 KB Output is correct
3 Correct 72 ms 2876 KB Output is correct
4 Incorrect 114 ms 12660 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 1089 ms 48168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 1380 KB Output is correct
2 Execution timed out 1085 ms 54452 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 1044 KB Output is correct
2 Execution timed out 1085 ms 76320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 952 KB Output is correct
2 Execution timed out 1088 ms 80592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 916 KB Output is correct
2 Execution timed out 1087 ms 84968 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 844 KB Output is correct
2 Execution timed out 1074 ms 93724 KB Time limit exceeded
3 Halted 0 ms 0 KB -