oj.uz

Submission #198171

# Submission time Handle Problem Language Result Execution time Memory
198171 2020-01-25T02:19:32 Z model_code Swimming competition (LMIO18_plaukimo_varzybos) C++14
100 / 100
 1008 ms 12452 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 48 ms 1144 KB Output is correct
3 Correct 9 ms 376 KB Output is correct
4 Correct 720 ms 8268 KB Output is correct
5 Correct 670 ms 8184 KB Output is correct
6 Correct 71 ms 1176 KB Output is correct
7 Correct 608 ms 7620 KB Output is correct
8 Correct 1 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 48 ms 1144 KB Output is correct
3 Correct 9 ms 376 KB Output is correct
4 Correct 720 ms 8268 KB Output is correct
5 Correct 670 ms 8184 KB Output is correct
6 Correct 71 ms 1176 KB Output is correct
7 Correct 608 ms 7620 KB Output is correct
8 Correct 1 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 21 ms 572 KB Output is correct
12 Correct 21 ms 804 KB Output is correct
13 Correct 34 ms 888 KB Output is correct
14 Correct 62 ms 1036 KB Output is correct
15 Correct 268 ms 5752 KB Output is correct
16 Correct 640 ms 6648 KB Output is correct
17 Correct 69 ms 888 KB Output is correct
18 Correct 40 ms 888 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 866 ms 8164 KB Output is correct
21 Correct 860 ms 8088 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 380 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 2 ms 376 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 48 ms 1144 KB Output is correct
3 Correct 9 ms 376 KB Output is correct
4 Correct 720 ms 8268 KB Output is correct
5 Correct 670 ms 8184 KB Output is correct
6 Correct 71 ms 1176 KB Output is correct
7 Correct 608 ms 7620 KB Output is correct
8 Correct 1 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 21 ms 572 KB Output is correct
12 Correct 21 ms 804 KB Output is correct
13 Correct 34 ms 888 KB Output is correct
14 Correct 62 ms 1036 KB Output is correct
15 Correct 268 ms 5752 KB Output is correct
16 Correct 640 ms 6648 KB Output is correct
17 Correct 69 ms 888 KB Output is correct
18 Correct 40 ms 888 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 866 ms 8164 KB Output is correct
21 Correct 860 ms 8088 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 380 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 24 ms 868 KB Output is correct
33 Correct 395 ms 5420 KB Output is correct
34 Correct 341 ms 5116 KB Output is correct
35 Correct 1008 ms 12452 KB Output is correct
36 Correct 728 ms 12324 KB Output is correct
37 Correct 711 ms 11604 KB Output is correct
38 Correct 432 ms 5964 KB Output is correct