oj.uz

Submission #997446

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

using namespace std;
using ll = long long;

constexpr ll pres = 1e5;
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 3 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 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 276 ms 4788 KB Output is correct
10 Correct 240 ms 4820 KB Output is correct
11 Correct 164 ms 4996 KB Output is correct
12 Correct 301 ms 4800 KB Output is correct
13 Correct 148 ms 4552 KB Output is correct
14 Correct 350 ms 4884 KB Output is correct
15 Correct 244 ms 4440 KB Output is correct
16 Runtime error 59 ms 4784 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 1555 ms 616 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 1555 ms 616 KB Time limit exceeded
2 Halted 0 ms 0 KB -