Submission #1140254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140254		tmm	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	100 / 100	426 ms	4648 KiB

plaukimo_varzybos

#include <iostream>
#include <algorithm>
#include <bitset>

using namespace std;
const int N_max = 1e6 + 5;

int n, A, B;
int v[N_max];

void reading(){
    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    sort(v + 1, v + n + 1);
}
bitset<N_max> propusi;
void reset(){
    for(int i = 0; i < N_max; i++)
        propusi[i] = 0;
}

int findNext(int poz){
    while(propusi[poz] == 0 && poz <= n)poz++;
    return poz;
}
bool verif(int i, int st, int md){
    if(st <= n && !(v[i] - v[st] <= md && i - st + 1 <= B))
        return 1;
    return 0;
}
bool isPossible(int maxDifference){
    reset();
    propusi[1] = 1;
    int st = 1; // startar
    for(int i = 1; i <= n && st <= n; i++){
        while(verif(i, st, maxDifference))
            st = findNext(st + 1);
        if(i - st + 1 < A) continue;
        propusi[i + 1] = 1;
    }
    if(propusi[n + 1] == 1)
        return 1;
    return 0;
}

int main(){
    reading();
    int L = 0, R = N_max, sol = R;
    while(L <= R){
        int M = (L + R) / 2;
        if(isPossible(M)){
            sol = M;
            R = M - 1;
        }else
            L = M + 1;
    }
    cout << sol;
}

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