Submission #198171

#	Time	Username	Problem	Language	Result	Execution time	Memory
198171		model_code	Swimming competition (LMIO18_plaukimo_varzybos)	C++14	100 / 100	1008 ms	12452 KiB

plaukimo_varzybos

#include <iostream>
#include <algorithm>
#include <queue>

//#define INPUT_FILE

#ifdef INPUT_FILE
#include <fstream>
#endif

const long MAX_N = 1000000;

long n, a, b;
long swtime[MAX_N];

// Funkcija patikrina, ar galima sudėlioti dalyvius taip, kad
// maksimalus skirtumas tarp lėčiausio ir greičiausio būtų 
// d_test ar mažesnis.
bool assign_groups(long d_test) {
    std::queue<long> groups;
    groups.push(-1);

    long i = a - 1;
    // Iš eilės einame nuo greičiausio iki lėčiausio ir bandome grupuoti.
    // Tinkamas rastas grupes saugoje eilėje "groups".
    // Algoritmo sudėtingumas - O(N)
    while (i < n && !groups.empty()) {
        if (i - groups.front() >= a) {
            if (i - groups.front() <= b && (swtime[i] - swtime[groups.front() + 1]) <= d_test) {
                // Grupė (nuo i iki groups.front()) yra leidžiamo ilgio bei
                // laikų skirtumas tarp lėčiausio ir greičiausio neviršija d_test.
                // Įsimename.
                groups.push(i);
                i++;
            }
            else
                // grupė tarp i ir groups.front() yra per ilga, todėl group.front() išmetame
                // kaip nebetinkamą tolimesniems grupavimams.
                groups.pop();
        }
        else
            i++;
    }

    // Tikriname, ar paskutinis plaukikas buvo įtrauktas į vieną iš grupių.
    return (!groups.empty() && groups.back() == n - 1);
}

int main() {

#ifdef INPUT_FILE
    std::ifstream in("plaukimo-varzybos.in");
    std::cin.rdbuf(in.rdbuf()); //redirect std::cin to in.txt!

    std::ofstream out("out.txt");
    std::cout.rdbuf(out.rdbuf()); //redirect std::cout to out.txt!
#endif

    std::cin >> n >> a >> b;

    for (long i = 0; i < n; i++)
        std::cin >> swtime[i];

    std::sort(swtime, swtime + n);

    // Vykdysime dvejetainę paiešką. dl, dh - mažiausias ir didžiausias galimi sprendiniai 
    // (tikrinamo intervalo rėžiai).
    long dl = 0, // Pasirenkame 0 kaip mažiausią pradinį rėžį.
        dh = swtime[n - 1] - swtime[0]; // Didžiausias rėžis - laikas tarp greičiausio ir lėčiausio plaukikų.
    while (dl != dh) { // Baigiame, kai rėžiai tampa lygūs.
        long d_test = (dh + dl) / 2; // Tikriname intervalo vidurį (dvejetainės paieškos principas).
        if (assign_groups(d_test))
            dh = d_test; // Taip, tai yra galimas sprendinys, todėl jis patampa nauja intervalo pabaiga.
        else
            // Ne, d_test sprendinys negalimas. Mažiausias galimas sprendinys bus nemažesnis nei d_test+1.
            dl = d_test + 1;
    }

    // dl = dh reikėtų taip pat patikrinti, jei sąlygoje nebūtų parašyta, kad sprendinys visada egzistuoja.
    std::cout << dl;

#ifdef INPUT_FILE
    in.close();
    out.close();
#endif

    return 0;
}

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