Submission #859815

#	Time	Username	Problem	Language	Result	Execution time	Memory
859815		Alexandruabcde	Measures (CEOI22_measures)	C++14	0 / 100	132 ms	6996 KiB

Main

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;
typedef long double LD;
typedef long long LL;
constexpr LD INF = 1LL * 1e16;

int N, M;
LD D;
LD A[NMAX];
LD B[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> D;
    for (int i = 1; i <= N; ++ i )
        cin >> A[i];
    for (int i = 1; i <= M; ++ i )
        cin >> B[i];
}

bool Check (LD t, int m) {
    LD first_dist = A[1] - t;

    for (int i = 2; i <= N + m; ++ i ) {
        LD next_dist = max(first_dist + D, A[i] - t);

        if (next_dist < A[i] - t || next_dist > A[i] + t) return false;

        first_dist = next_dist;
    }

    return true;
}

void Solve_FirstCase () {
    sort(A+1, A+N+1);

    for (int i = 1; i <= M; ++ i ) {
        A[N+i] = B[i];
        sort(A+1, A+N+i+1);

        LL st = 0, dr = INF;
        LD ans = 0;

        while (st <= dr) {
            LL mij = (st + dr) / 2;

            if (Check((LD)mij*.5, i)) {
                dr = mij - 1;
                ans = mij * .5;
            }
            else st = mij + 1;
        }

        cout << ans << " ";
    }
}

void Solve_SecondCase () {
    LD worst_case = -INF;
    LD answer = 0;

    for (int j = 1; j <= M; ++ j ) {
        LD new_pos_ans = 1LL * j * D - B[j] + worst_case;

        answer = max(answer, (LD)new_pos_ans * .5);

        cout << answer << " ";

        worst_case = max(worst_case, B[j] - 1LL * j * D);
    }
}

int main()
{
    Read();
    if (M <= 10) Solve_FirstCase();
    else Solve_SecondCase();

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41