oj.uz

Submission #997447

# Submission time Handle Problem Language Result Execution time Memory
997447 2024-06-12T10:29:43 Z crafticat Measures (CEOI22_measures) C++17
10 / 100
 1500 ms 3584 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll pres = 1e4;
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 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 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 372 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 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 372 KB Output is correct
9 Correct 276 ms 3584 KB Output is correct
10 Correct 232 ms 3524 KB Output is correct
11 Correct 152 ms 3524 KB Output is correct
12 Correct 310 ms 3524 KB Output is correct
13 Correct 141 ms 3532 KB Output is correct
14 Correct 327 ms 3520 KB Output is correct
15 Correct 241 ms 3520 KB Output is correct
16 Runtime error 60 ms 3516 KB Execution failed because the return code was nonzero
17 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 592 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 1584 ms 592 KB Time limit exceeded
2 Halted 0 ms 0 KB -