Submission #1140165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140165		andrei_hq	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	0 / 100	0 ms	328 KiB

plaukimo_varzybos

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

#define MAXN 1000000
#define MAXVAL 1000000

using namespace std;

int times[MAXN], groups[MAXN];
int n, a, b;

int cautbin2(int st, int dr, int val){
    int capat=dr;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(times[mij]>=val){
            dr=mij;
        }
        else{
            st=mij;
        }
    }
    return capat-dr+1;
}

bool check(int val){
    int cnt=0, prim_elem, i=0, j=0, flag=1, nr_elem, minn;
    while(i<n&&flag==1){
        if(cnt==0){
            cnt++;
            prim_elem=times[i];
        }
        else{
            if(times[i]-prim_elem<=val){
                cnt++;
                if(cnt==a){
                    groups[j++]=a;
                    cnt=0;
                }
            }
            else{
                if(j==0){
                    flag=0;
                }
                else{
                    while(times[i]-times[i-cnt]>val){
                        groups[j-1]++;
                        cnt--;
                    }
                    prim_elem=times[i-cnt];
                    cnt++;
                }
            }
        }
        i++;
    }
    if(flag==1){
        if(cnt>0){
            groups[j-1]+=cnt;
        }
        j--;
        cnt=0;
        while(j>0&&flag==1){
            minn=min(groups[j], b);
            nr_elem=cautbin2(n-1-(cnt+minn), n-1-cnt, abs(times[n-1-cnt]-val));
            groups[j-1]+=groups[j]-nr_elem;
            groups[j]=nr_elem;
            cnt+=groups[j];
            if(groups[j]<a){
                flag=1;
            }
            j--;
        }
        if(flag==1&&(groups[0]>b||times[n-1-cnt]-times[0]>val)){
            flag=0;
        }
    }
    return flag;
}

int cautbin(){
    int st=-1, dr=times[n-1]-times[0];
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(mij)){
            dr=mij;
        }
        else{
            st=mij;
        }
    }
    return dr;
}

int main()
{
    int i;
    scanf("%d%d%d", &n, &a, &b);
    for(i=0;i<n;i++){
        scanf("%d", &times[i]);
    }
    sort(times, times+n);
    printf("%d", cautbin());
    return 0;
}

Compilation message (stderr)

plaukimo_varzybos.cpp: In function 'int main()':
plaukimo_varzybos.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d%d", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plaukimo_varzybos.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf("%d", &times[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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