oj.uz

Submission #997448

# Submission time Handle Problem Language Result Execution time Memory
997448 2024-06-12T10:31:07 Z crafticat Measures (CEOI22_measures) C++17
24 / 100
 1500 ms 4036 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll pres = 1e2;
constexpr ll inf = (1e18);
constexpr ll epsilon = 1;

ll d;

bool ok(vector<ll> &arr, ll move) {
    ll lastPos = -inf;
    for (auto x : arr) {
        ll req = (lastPos + d) - x;
        req = max(req, -move);
        if (req > move) return false;
        lastPos = x + req;
    }
    return true;
}

double solve(vector<ll> arr) {
    std::sort(arr.begin(), arr.end());

    ll l = 0, r = inf;
    while (r - l > 0) {
        ll mid = l + (r - l) / 2;
        if (ok(arr,mid)) {
            r = mid;
        } else {
            l = mid + epsilon;
        }
    }
    return l;
}

void printAns(ll ans) {
    cout << ans / pres;
    ans %= pres;
    if (ans != 0) cout << ".";
    ll mul = pres;
    while (ans != 0) {
        mul /= 10;
        cout << (ans / mul) % 10;
        ans %= mul;
    }
}

int main() {
    ll n, m; cin >> n >> m >> d;

    vector<ll> p;
    for (ll i = 0; i < n; ++i) {
        ll x; cin >> x;
        x *= pres;
        p.push_back(x);
    }

    d*=pres;

    for (ll i = 0; i < m; ++i) {
        ll x; cin >> x;
        x *= pres;
        p.push_back(x);
        ll ans = solve(p);
        if (ans >= inf / 2) exit(5);
        printAns(ans);
        cout << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 456 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 456 KB Output is correct
9 Correct 268 ms 3584 KB Output is correct
10 Correct 221 ms 3528 KB Output is correct
11 Correct 143 ms 3524 KB Output is correct
12 Correct 293 ms 3440 KB Output is correct
13 Correct 129 ms 3520 KB Output is correct
14 Correct 323 ms 3524 KB Output is correct
15 Correct 228 ms 3516 KB Output is correct
16 Correct 152 ms 4036 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 576 KB Time limit exceeded
2 Halted 0 ms 0 KB -