oj.uz

답안 #1098003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1098003 2024-10-08T19:31:06 Z 0x34c Mobile (BOI12_mobile) C++17
50 / 100
 1000 ms 100784 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define ld long double
#define pdd pair<ld, ld>

using namespace std;

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

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

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 l = -1, r = INF;
        while ((r - l) > eps)
        {
            ld m = l + (r - l) / 2;

            ld d1 = dist(pts[idx1], m), d2 = dist(pts[idx2], m);
            if (d1 < d2)
                l = m;
            else
                r = m;
        }

        return l + (r - l) / 2LL;
    };

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

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

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

    ld mx_dist = 0;
    for (int i = 0; i < 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], 0));
        mn_end = min(mn_end, dist(pts[i], 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:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < bps.size(); i++)
      |                     ~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 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 #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 732 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 604 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 604 KB Output is correct
2 Correct 12 ms 836 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 13 ms 836 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 12 ms 604 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 13 ms 836 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 860 KB Output is correct
2 Correct 12 ms 840 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 13 ms 600 KB Output is correct
5 Correct 2 ms 344 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 6208 KB Output is correct
2 Correct 152 ms 4304 KB Output is correct
3 Correct 129 ms 4056 KB Output is correct
4 Correct 196 ms 5580 KB Output is correct
5 Correct 9 ms 856 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1372 KB Output is correct
2 Correct 100 ms 3024 KB Output is correct
3 Correct 185 ms 5320 KB Output is correct
4 Correct 206 ms 5660 KB Output is correct
5 Correct 230 ms 6356 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 10440 KB Output is correct
2 Correct 146 ms 4056 KB Output is correct
3 Correct 116 ms 9680 KB Output is correct
4 Correct 268 ms 7024 KB Output is correct
5 Correct 60 ms 2140 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 3796 KB Output is correct
2 Correct 129 ms 3836 KB Output is correct
3 Correct 49 ms 2668 KB Output is correct
4 Correct 265 ms 6856 KB Output is correct
5 Correct 220 ms 6104 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 11216 KB Output is correct
2 Correct 132 ms 3808 KB Output is correct
3 Correct 50 ms 2668 KB Output is correct
4 Correct 269 ms 6852 KB Output is correct
5 Correct 225 ms 6100 KB Output is correct

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 791 ms 54832 KB Output is correct
2 Correct 130 ms 4944 KB Output is correct
3 Correct 126 ms 4824 KB Output is correct
4 Execution timed out 1006 ms 32056 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 4872 KB Output is correct
2 Execution timed out 1042 ms 42684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 956 ms 74276 KB Output is correct
2 Correct 136 ms 14676 KB Output is correct
3 Correct 131 ms 14164 KB Output is correct
4 Execution timed out 1029 ms 53588 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 5448 KB Output is correct
2 Execution timed out 1043 ms 49424 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1065 ms 81196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 6228 KB Output is correct
2 Execution timed out 1083 ms 64684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1052 ms 87096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 7000 KB Output is correct
2 Execution timed out 1102 ms 72468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1078 ms 100784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 8532 KB Output is correct
2 Execution timed out 1059 ms 86468 KB Time limit exceeded
3 Halted 0 ms 0 KB -