oj.uz

Submission #684206

# Submission time Handle Problem Language Result Execution time Memory
684206 2023-01-20T16:26:09 Z Brownbear2710 Mobile (BOI12_mobile) C++14
0 / 100
 1000 ms 81152 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 = 2e9;
        while(abs(lo-hi) > 0.0001)
        {
            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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 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 2 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 4 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 1108 KB Output is correct
2 Correct 12 ms 912 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 6 ms 936 KB Output is correct
5 Incorrect 2 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 150 ms 8864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 10116 KB Output is correct
2 Correct 151 ms 6000 KB Output is correct
3 Correct 137 ms 9036 KB Output is correct
4 Correct 89 ms 10644 KB Output is correct
5 Incorrect 51 ms 2456 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 5172 KB Output is correct
2 Correct 143 ms 5196 KB Output is correct
3 Correct 66 ms 1760 KB Output is correct
4 Incorrect 90 ms 10696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 10760 KB Output is correct
2 Correct 148 ms 5176 KB Output is correct
3 Correct 63 ms 1812 KB Output is correct
4 Incorrect 92 ms 10704 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 1086 ms 48492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 1584 KB Output is correct
2 Execution timed out 1088 ms 47956 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 1086 ms 68600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 1220 KB Output is correct
2 Execution timed out 1091 ms 68240 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 1092 ms 71628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 1016 KB Output is correct
2 Execution timed out 1086 ms 71340 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 1081 ms 75032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 1160 KB Output is correct
2 Execution timed out 1096 ms 74448 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 1087 ms 81152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 1280 KB Output is correct
2 Execution timed out 1091 ms 80340 KB Time limit exceeded
3 Halted 0 ms 0 KB -