oj.uz

Submission #677429

# Submission time Handle Problem Language Result Execution time Memory
677429 2023-01-03T09:46:03 Z stanislavpolyn Measures (CEOI22_measures) C++17
24 / 100
 1500 ms 5196 KB 
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? (a = b, 1) : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 3e5 + 5;

int n, m;
ll d;
ll a[N];
ll b[N];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> m >> d;

    d *= 2;

    fr (i, 1, n) {
        cin >> a[i];
        a[i] *= 2;
    }

    fr (i, 1, m) {
        ll x;
        cin >> x;
        x *= 2;
        a[++n] = x;
        sort(a + 1, a + 1 + n);

        auto possible = [&](ll t) {
            fr (i, 1, n) b[i] = a[i];

            fr (i, 1, n) {
                ll have = t;
                if (i > 1) {
                    ll x = b[i] - b[i - 1];
                    if (x < d) {
                        if (d - x > t) {
                            return 0;
                        }
                        have -= max(0LL, d - x);
                        b[i] = b[i - 1] + d;
                    }
                }
                if (i == 1 || b[i] - b[i - 1] > d) {
                    if (i == 1) b[i] -= t;
                    else b[i] -= min(b[i] - b[i - 1] - d, have);
                }
            }
            return 1;
        };

        ll l = 0;
        ll r = 1e18;
        while (l < r) {
            ll mid = l + ((r - l) >> 1);
            if (possible(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        assert(possible(l));

        cout << l / 2;
        if (l % 2) cout << ".5";
        cout << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 8 ms 372 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 7 ms 368 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 8 ms 372 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 7 ms 368 KB Output is correct
9 Correct 659 ms 5116 KB Output is correct
10 Correct 639 ms 5196 KB Output is correct
11 Correct 553 ms 5028 KB Output is correct
12 Correct 659 ms 4976 KB Output is correct
13 Correct 595 ms 4516 KB Output is correct
14 Correct 622 ms 4900 KB Output is correct
15 Correct 650 ms 4508 KB Output is correct
16 Correct 532 ms 4932 KB Output is correct

Subtask #3
0 / 35.0

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