oj.uz

Submission #859815

# Submission time Handle Problem Language Result Execution time Memory
859815 2023-10-10T17:39:22 Z Alexandruabcde Measures (CEOI22_measures) C++14
0 / 100
 132 ms 6996 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2392 KB Output is correct
2 Incorrect 7 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2392 KB Output is correct
2 Incorrect 7 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 5712 KB Output is correct
2 Incorrect 132 ms 6996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 5712 KB Output is correct
2 Incorrect 132 ms 6996 KB Output isn't correct
3 Halted 0 ms 0 KB -