Submission #1140058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140058		argon1	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	10 / 100	246 ms	4328 KiB

plaukimo_varzybos

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
int times[MAX_N+5];
int N, A, B;

bool isFeasible(int maxDiff) {
    int groupCount = 0; // Count of groups formed
    int groupStart = 0; // Index of the start of the current group

    for (int i = 0; i < N; ++i) {
        // If the current swimmer can't be added due to exceeding maxDiff
        if (times[i] - times[groupStart] > maxDiff || i - groupStart + 1 > B) {
            // Check if the previous group size is valid
            if (i - groupStart < A) return false;
            // Start a new group
            groupStart = i;
            ++groupCount;
        }
    }

    // Check the size of the last group
    if (N - groupStart < A) return false;

    return true;
}

int main() {

    cin >> N >> A >> B;

    for (int i = 0; i < N; ++i) {
        cin >> times[i];
    }

    //Sort
    sort(times, times + N);

    //Binary search for the minimum maximum difference
    int low = 0;
    int high = times[N - 1] - times[0];
    int result = high;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if this mid value is feasible
        if (isFeasible(mid)) {
            result = mid; // Update result and try for a smaller maximum difference
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << result << "\n";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40