oj.uz

Submission #1098021

# Submission time Handle Problem Language Result Execution time Memory
1098021 2024-10-08T19:57:50 Z 0x34c Mobile (BOI12_mobile) C++17
95 / 100
 586 ms 131072 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll
#define ld long double
#define pdd pair<ld, ld>

using namespace std;

int dist2(pii a, pii b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

ld dist(pii a, ld x)
{
    ld x1 = a.first, y = a.second;
    return sqrt((x1 - x) * (x1 - x) + y * y);
}

const int INF2 = 1e12;
const int INF = 1e9 + 1;
ld eps = 1e-4;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, L;
    cin >> N >> L;

    vector<pii> inp(N);
    map<int, int> closest;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;

        inp[i] = {x, y};

        if (!closest.count(x))
            closest[x] = y;
        else
            closest[x] = (abs(closest[x]) > abs(y) ? y : closest[x]);
    }

    vector<pii> pts;
    for (pii p : closest)
        pts.push_back(p);

    N = pts.size();

    auto calc_bp = [&](int idx1, int idx2)
    {
        ld x1 = pts[idx1].first, y1 = pts[idx1].second;
        ld x2 = pts[idx2].first, y2 = pts[idx2].second;

        if (x1 - x2 == 0)
            return (ld)-1;
        return ((ld)0.5) * (x1 + x2 + (y1 * y1 - y2 * y2) / (x1 - x2));
    };

    stack<int> stk;
    stk.push(0);
    vector<ld> dists, bps;
    for (int i = 1; i < N; i++)
    {
        ld bp = calc_bp(stk.top(), i);
        bool emp = false;

        while (!bps.empty() && bps.back() >= bp)
        {
            bps.pop_back();
            stk.pop();
            dists.pop_back();
            if (stk.empty())
                emp = true;
            else
                bp = calc_bp(stk.top(), i);
        }

        if (!emp)
        {
            bps.push_back(bp);
            dists.push_back(dist(pts[i], bp));
        }
        stk.push(i);
    }

    ld mx_dist = 0;
    for (int i = 0; i < (bps.empty() ? 0 : bps.size()); i++)
    {
        if (bps[i] < 0 || bps[i] > L)
            continue;
        mx_dist = max(mx_dist, dists[i]);
    }

    ld mn_start = INF2, mn_end = INF2;
    for (int i = 0; i < N; i++)
    {
        mn_start = min(mn_start, dist(pts[i], (ld)0));
        mn_end = min(mn_end, dist(pts[i], (ld)L));
    }

    mx_dist = max({mx_dist, mn_start, mn_end});
    cout << setprecision(4) << fixed << mx_dist << endl;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:93:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'long unsigned int' [-Wsign-compare]
   93 |     for (int i = 0; i < (bps.empty() ? 0 : bps.size()); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 844 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 1072 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 1112 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 920 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 1 ms 464 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8836 KB Output is correct
2 Correct 32 ms 7264 KB Output is correct
3 Correct 26 ms 6352 KB Output is correct
4 Correct 40 ms 9668 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2720 KB Output is correct
2 Correct 28 ms 5584 KB Output is correct
3 Correct 37 ms 9164 KB Output is correct
4 Correct 37 ms 9932 KB Output is correct
5 Correct 40 ms 10868 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15052 KB Output is correct
2 Correct 34 ms 7116 KB Output is correct
3 Correct 36 ms 13516 KB Output is correct
4 Correct 49 ms 12244 KB Output is correct
5 Correct 29 ms 4312 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7372 KB Output is correct
2 Correct 40 ms 7092 KB Output is correct
3 Correct 33 ms 4688 KB Output is correct
4 Correct 47 ms 12232 KB Output is correct
5 Correct 44 ms 10432 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 14020 KB Output is correct
2 Correct 40 ms 7116 KB Output is correct
3 Correct 34 ms 4908 KB Output is correct
4 Correct 47 ms 12372 KB Output is correct
5 Correct 48 ms 10680 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 74724 KB Output is correct
2 Correct 158 ms 16720 KB Output is correct
3 Correct 161 ms 16212 KB Output is correct
4 Correct 275 ms 57460 KB Output is correct
5 Correct 259 ms 43708 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 17236 KB Output is correct
2 Correct 258 ms 56236 KB Output is correct
3 Correct 229 ms 27340 KB Output is correct
4 Correct 275 ms 57020 KB Output is correct
5 Correct 305 ms 52160 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 104012 KB Output is correct
2 Correct 178 ms 19708 KB Output is correct
3 Correct 180 ms 19024 KB Output is correct
4 Correct 332 ms 75716 KB Output is correct
5 Correct 307 ms 45244 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 20304 KB Output is correct
2 Correct 314 ms 71352 KB Output is correct
3 Correct 266 ms 26596 KB Output is correct
4 Correct 347 ms 75644 KB Output is correct
5 Correct 335 ms 68388 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 117400 KB Output is correct
2 Correct 208 ms 22780 KB Output is correct
3 Correct 200 ms 22096 KB Output is correct
4 Correct 406 ms 85092 KB Output is correct
5 Correct 345 ms 45316 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 23376 KB Output is correct
2 Correct 369 ms 80376 KB Output is correct
3 Correct 333 ms 36484 KB Output is correct
4 Correct 388 ms 84928 KB Output is correct
5 Correct 402 ms 75448 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 130976 KB Output is correct
2 Correct 225 ms 25684 KB Output is correct
3 Correct 225 ms 24960 KB Output is correct
4 Correct 480 ms 95160 KB Output is correct
5 Correct 403 ms 63680 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 26596 KB Output is correct
2 Correct 433 ms 89212 KB Output is correct
3 Correct 379 ms 38720 KB Output is correct
4 Correct 469 ms 94824 KB Output is correct
5 Correct 466 ms 82936 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 470 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 32992 KB Output is correct
2 Correct 552 ms 111072 KB Output is correct
3 Correct 500 ms 51516 KB Output is correct
4 Correct 586 ms 114368 KB Output is correct
5 Correct 566 ms 99776 KB Output is correct