oj.uz

Submission #684204

# Submission time Handle Problem Language Result Execution time Memory
684204 2023-01-20T16:25:06 Z Brownbear2710 Mobile (BOI12_mobile) C++14
0 / 100
 1000 ms 81148 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.00001)
        {
            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 0 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 0 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 5 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 4 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 18 ms 908 KB Output is correct
2 Correct 14 ms 916 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 7 ms 908 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 145 ms 8808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 10076 KB Output is correct
2 Correct 157 ms 5712 KB Output is correct
3 Correct 144 ms 9176 KB Output is correct
4 Correct 90 ms 10648 KB Output is correct
5 Incorrect 54 ms 3396 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 5296 KB Output is correct
2 Correct 148 ms 5184 KB Output is correct
3 Correct 66 ms 1808 KB Output is correct
4 Incorrect 107 ms 10684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 10764 KB Output is correct
2 Correct 148 ms 5204 KB Output is correct
3 Correct 78 ms 1836 KB Output is correct
4 Incorrect 108 ms 10696 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 1094 ms 48216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 1520 KB Output is correct
2 Execution timed out 1091 ms 47840 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 1101 ms 68452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 1196 KB Output is correct
2 Execution timed out 1083 ms 68348 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 71608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 936 KB Output is correct
2 Execution timed out 1092 ms 71416 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 1092 ms 74784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 1176 KB Output is correct
2 Execution timed out 1094 ms 74292 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 1090 ms 81148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 1020 KB Output is correct
2 Execution timed out 1083 ms 80448 KB Time limit exceeded
3 Halted 0 ms 0 KB -