oj.uz

Submission #1096190

# Submission time Handle Problem Language Result Execution time Memory
1096190 2024-10-04T04:42:12 Z Omar_Elgedawy Mobile (BOI12_mobile) C++17
100 / 100
 225 ms 64340 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ld long double
#define F first
#define S second
#define el '\n'
#define cout(x) for(auto v:x)cout<<v<<el
#define coutp(x) for(auto v:x)cout<<v.F<<' '<<v.S<<el
#define cin(x) for(auto &v:x)cin>>v;
#define pb(x) push_back(x)
#define all(x)  x.begin(),x.end()

const int N = 5e3 + 5, M = 1e2 + 5, Mod = 1e9 + 7;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};

int nxt()
{
    int x;
    cin >> x;
    return x;
}

ld midX(pair<ld,ld> a, pair<ld,ld> b)
{
    return (b.F * b.F + b.S * b.S - a.F * a.F - a.S * a.S) / (2 * b.F - 2 * a.F);
}

ld dist(pair<ld,ld> a, pair<ld,ld> b)
{
    return sqrtl((a.F - b.F) * (a.F - b.F) + (a.S - b.S) * (a.S - b.S));
}

void solve(int h)
{
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> v;
    ld x[n], y[n];
    deque<pair<ld,ld>> st;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        x[i] = a;
        y[i] = abs(b);
        if (st.size() && st.back().F == x[i])
        {
            if (st.back().S <= y[i])
            {
                continue;
            }
            else
            {
                st.pop_back();
            }
        }
        while (st.size() > 1 &&
            midX(st[st.size() - 2], st.back()) >
            midX(st.back(), {x[i], y[i]}))
        {
            st.pop_back();
        }
        st.push_back({x[i], y[i]});
    }
    while (st.size() > 1 &&
        midX(st[0], st[1]) < 0)
    {
        st.pop_front();
    }
    while (st.size() > 1 &&
        midX(st.back(), st[st.size() - 2]) > m)
    {
        st.pop_back();
    }
    ld mx = 0;
    for (int i = 0; i < st.size(); i++)
    {
        pair<ld,ld> left = {0, 0}, right = {m, 0};
        if (i)left.F = midX(st[i], st[i - 1]);
        if (i != st.size() - 1)right.F = midX(st[i], st[i + 1]);
        if (left.F < 0 || left.F > m || right.F < 0 || right.F > m)
            continue;
        mx = max({mx, dist(st[i], left), dist(st[i], right)});
    }
    cout << fixed<<setprecision(4)<<mx;
}

int32_t main()
{
// #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
 // #endif
    // freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; i++)solve(i);
    return 0;
}

Compilation message

mobile.cpp: In function 'void solve(long long int)':
mobile.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < st.size(); i++)
      |                     ~~^~~~~~~~~~~
mobile.cpp:83:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if (i != st.size() - 1)right.F = midX(st[i], st[i + 1]);
      |             ~~^~~~~~~~~~~~~~~~

Subtask #1
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 #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 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 600 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 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2908 KB Output is correct
2 Correct 14 ms 2652 KB Output is correct
3 Correct 12 ms 2652 KB Output is correct
4 Correct 18 ms 3932 KB Output is correct
5 Correct 6 ms 2404 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2908 KB Output is correct
2 Correct 12 ms 2664 KB Output is correct
3 Correct 15 ms 2908 KB Output is correct
4 Correct 17 ms 3936 KB Output is correct
5 Correct 18 ms 4440 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5980 KB Output is correct
2 Correct 13 ms 2908 KB Output is correct
3 Correct 15 ms 6356 KB Output is correct
4 Correct 23 ms 5468 KB Output is correct
5 Correct 14 ms 3932 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3584 KB Output is correct
2 Correct 15 ms 4984 KB Output is correct
3 Correct 13 ms 4956 KB Output is correct
4 Correct 25 ms 5368 KB Output is correct
5 Correct 18 ms 4852 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5460 KB Output is correct
2 Correct 15 ms 4956 KB Output is correct
3 Correct 14 ms 4956 KB Output is correct
4 Correct 22 ms 5476 KB Output is correct
5 Correct 19 ms 4700 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 32440 KB Output is correct
2 Correct 71 ms 23632 KB Output is correct
3 Correct 68 ms 23256 KB Output is correct
4 Correct 111 ms 25424 KB Output is correct
5 Correct 96 ms 22868 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15880 KB Output is correct
2 Correct 94 ms 24192 KB Output is correct
3 Correct 69 ms 24912 KB Output is correct
4 Correct 112 ms 25420 KB Output is correct
5 Correct 99 ms 23376 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 38660 KB Output is correct
2 Correct 87 ms 28376 KB Output is correct
3 Correct 80 ms 27796 KB Output is correct
4 Correct 133 ms 31056 KB Output is correct
5 Correct 107 ms 27144 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 19216 KB Output is correct
2 Correct 114 ms 28924 KB Output is correct
3 Correct 82 ms 27988 KB Output is correct
4 Correct 130 ms 30864 KB Output is correct
5 Correct 119 ms 27916 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 45132 KB Output is correct
2 Correct 94 ms 32952 KB Output is correct
3 Correct 92 ms 32336 KB Output is correct
4 Correct 151 ms 35664 KB Output is correct
5 Correct 117 ms 31168 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 22360 KB Output is correct
2 Correct 130 ms 33464 KB Output is correct
3 Correct 103 ms 34896 KB Output is correct
4 Correct 159 ms 35664 KB Output is correct
5 Correct 138 ms 32336 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 51464 KB Output is correct
2 Correct 129 ms 37928 KB Output is correct
3 Correct 130 ms 36948 KB Output is correct
4 Correct 188 ms 41040 KB Output is correct
5 Correct 155 ms 36492 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 25320 KB Output is correct
2 Correct 153 ms 37968 KB Output is correct
3 Correct 109 ms 38984 KB Output is correct
4 Correct 195 ms 40964 KB Output is correct
5 Correct 161 ms 36948 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 64340 KB Output is correct
2 Correct 146 ms 47084 KB Output is correct
3 Correct 148 ms 46136 KB Output is correct
4 Correct 225 ms 50768 KB Output is correct
5 Correct 191 ms 45140 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 31580 KB Output is correct
2 Correct 191 ms 47136 KB Output is correct
3 Correct 138 ms 48976 KB Output is correct
4 Correct 222 ms 51280 KB Output is correct
5 Correct 193 ms 46328 KB Output is correct