oj.uz

Submission #859809

# Submission time Handle Problem Language Result Execution time Memory
859809 2023-10-10T17:32:17 Z Alexandruabcde Measures (CEOI22_measures) C++14
0 / 100
 112 ms 5456 KB 
#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 (N == 0) {
        Solve_SecondCase();
    }
    else Solve_FirstCase();

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Incorrect 7 ms 484 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 344 KB Output is correct
2 Incorrect 7 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4012 KB Output is correct
2 Incorrect 112 ms 5456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4012 KB Output is correct
2 Incorrect 112 ms 5456 KB Output isn't correct
3 Halted 0 ms 0 KB -