Submission #1140212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140212		argon1	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	100 / 100	432 ms	6376 KiB

plaukimo_varzybos

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

const int MAX_N = 1e6 + 5;  // Dimensiunea maximă a array-ului
int swimmerTimes[MAX_N];    // Timpii înotătorilor
int numSwimmers, minGroupSize, maxGroupSize;  // Numărul de înotători și limitele grupurilor

// Verifică dacă putem împărți înotătorii cu o diferență maximă de `maxDiff`
bool canGroupWithMaxDiff(int maxDiff) {
    deque<int> validWindow;  // Deque pentru gestionarea ferestrei valide
    int right = minGroupSize;  // Indexul capătului din dreapta al grupului curent
    validWindow.push_front(1); // Adăugăm primul înotător în fereastra validă

    while (right <= numSwimmers && !validWindow.empty()) {
        // Dacă dimensiunea grupului curent este suficient de mare
        if (right - validWindow.front() + 1 >= minGroupSize) {
            // Dacă grupul curent este valid și respectă constrângerile
            if (right - validWindow.front() + 1 <= maxGroupSize && 
                swimmerTimes[right] - swimmerTimes[validWindow.front()] <= maxDiff) {
                // Extindem grupul spre dreapta
                right++;
                validWindow.push_back(right);
            } else {
                // Dacă grupul nu este valid, eliminăm din partea stângă
                validWindow.pop_front();
            }
        } else {
            // Dacă grupul este prea mic, extindem grupul spre dreapta
            right++;
        }
    }

    // Verificăm dacă am reușit să grupăm toți înotătorii valid
    if (validWindow.empty() || validWindow.back() != numSwimmers + 1) {
        return false;
    }
    return true;
}

int main() {
    cin >> numSwimmers >> minGroupSize >> maxGroupSize;

    // Citim timpii înotătorilor
    for (int i = 1; i <= numSwimmers; i++) {
        cin >> swimmerTimes[i];
    }

    // Sortăm timpii
    sort(swimmerTimes + 1, swimmerTimes + numSwimmers + 1);

    // Binary search pe diferența maximă permisă
    int left = 0, right = swimmerTimes[numSwimmers] - swimmerTimes[1], result = 0;

    while (left <= right) {
        int mid = (left + right) / 2;  // Diferența maximă curentă
        if (canGroupWithMaxDiff(mid)) {
            result = mid;  // Salvează soluția validă
            right = mid - 1;  // Încearcă o diferență mai mică
        } else {
            left = mid + 1;  // Încearcă o diferență mai mare
        }
    }

    // Afișăm rezultatul final
    cout << result << endl;

    return 0;
}

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