Submission #1347082

#TimeUsernameProblemLanguageResultExecution timeMemory
1347082BoomydayMeasures (CEOI22_measures)C++20
0 / 100
1594 ms2264 KiB
//
// Created by adavy on 4/4/2026.
//


#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define int long long

bool is_good(vector<ll>& vec, ll D, ll ans){


    // assume the vector is sorted

    ll pos;

    pos = vec[0] - ans;

    for(int i=1;i<vec.size();++i){

        ll nxtpos = max(pos+D, vec[i]-ans);
        if (nxtpos > vec[i] + ans){
            return false;
        }
        pos = nxtpos;
    }
    return true;
}

ll solve(vector<ll> vec, ll D){
    // binary search on the answer

    ll mn = 0;
    ll mx = 1e18;

    while (mn < mx){

        ll md = (mn + mx)/2;
        if (is_good(vec, D, md)){
            mx = md;
        }
        else mn = md + 1;
    }
    return mn;


}

signed main(){
    ll N, M, D; cin >> N >> M >> D;
    vector<ll> A(N);
    vector<ll> B(M);

    D *= 8;
    for(int i=0;i<N;++i){
        cin >> A[i]; A[i] *= 8;
    }
    for(int i=0;i<M;++i){
        cin >> B[i]; B[i] *= 8;
    }

    vector<ll> anses;

    for(int i=0;i<M;++i){
        A.push_back(B[i]);
        sort(A.begin(), A.end());
        anses.push_back(solve(A, D));
    }

    for(auto&ans:anses){
        cout << ((long double)ans)/8.0 << " ";
    }
    cout << endl;





}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...