Submission #1330247

#TimeUsernameProblemLanguageResultExecution timeMemory
1330247shirokuma5Measures (CEOI22_measures)C++20
24 / 100
1595 ms3540 KiB
/*# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")*/
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll mod = 998244353;
const ll INF = 1LL << 60;
const int MAX = 1e9 + 10;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); i++)
#define repd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repd1(i, n) for (int i = (int)(n); i >= 1; i--)
#define repd2(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); i--)

template<class T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b; return 1;
    }
    return 0;
}
template<class T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b; return 1;
    }
    return 0;
}
struct edge {
    int to, w;
};
ll inv(ll a) {
    ll b = mod, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= b * t;
        swap(a, b);
        u -= v * t;
        swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}
template<class T> void print(vector<T> a) {
    int n = a.size();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
}
template<class T> int low_idx(const vector<T> &a, T x) {
    return distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
template<class T> bool next_combination(T &bit, int N) {
    T x = bit & -bit, y = bit + x;
    bit = (((bit & ~y) / x) >> 1) | y;
    return (bit < (1LL << N));
}
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, d; cin >> n >> m >> d; d *= 2;
    vector<ll> a(n), b(m);
    rep(i, n) {
        cin >> a[i]; a[i] *= 2;
    }
    rep(i, m) {
        cin >> b[i]; b[i] *= 2;
    }

    rep(i, m) {
        a.push_back(b[i]); n++;
        sort(a.begin(), a.end());
        ll l = 0, r = (ll)d * n;
        while (r - l > 0) {
            ll mid = (l + r) / 2;
            ll cur = a[0] - mid;
            bool flag = 1;
            rep1(j, n - 1) {
                if (a[j] + mid - cur < d) flag = 0;
                cur = max(a[j] - mid, cur + d);
            }
            if (flag) r = mid;
            else l = mid + 1;
        }
        cout << l / 2;
        if (l % 2 == 1) cout << ".5";
        if (i == m - 1) cout << endl;
        else cout << " ";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...