Submission #859810

#	Time	Username	Problem	Language	Result	Execution time	Memory
859810		Alexandruabcde	Measures (CEOI22_measures)	C++14	0 / 100	112 ms	3444 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

int N, M, D;
int A[NMAX];
int 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 = -INF;
    int i = 1, j = 1;

    while (i <= N || j <= m) {
        LD next_dist = 0;

        if (i <= N && (A[i] <= B[j] || j > m)) {
            next_dist = max(first_dist + D, A[i] - t);

            if (next_dist < A[i] - t || next_dist > A[i] + t) return false;
            ++ i;
        }
        else {
            next_dist = max(first_dist + D, B[j] - t);

            if (next_dist < B[j] - t || next_dist > B[j] + t) return false;
            ++ j;
        }

        first_dist = next_dist;
    }

    return true;
}

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

    for (int i = 1; i <= M; ++ i ) {
        sort(B+1, B+i+1);

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

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

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

        cout << ans << " ";
    }
}

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

    for (int j = 1; j <= M; ++ j ) {
        LL 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