Submission #1160933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160933		Kalata_56	Gap (APIO16_gap)	C++20	100 / 100	40 ms	1864 KiB

gap

#include<bits/stdc++.h>
using namespace std;
#include "gap.h"
long long mas[100011];

long long findGap(int T,int N){
    if(T==1){
    long long maxa=1e18+1;
    long long ans=0;
    long long l=0,r=1e18;
    long long L=0,R=N-1;
    while(L<=R){
        //long long k1,k2;
        MinMax(l,r,&mas[L],&mas[R]);
        L++;
        R--;
        l=mas[L-1]+1;
        r=mas[R+1]-1;
    }
    for(int i=0;i<N-1;i++){
        if(mas[i+1]-mas[i]>ans){
            ans=mas[i+1]-mas[i];
        }
    }
    return ans;
    }
    long long k1,k2;
    long long l=0,r=1e18;
    MinMax(l,r,&k1,&k2);
    if(N==2){
        return k2-k1;
    }

    l=k1+1;
    r=k2-1;
    long long dul=(r-l+1)/(N-1)+1;

    long long L=l,R=min(L+dul-1,r-1);
    long long pre=l-1;
    long long otg=0;
    for(int i=0;R<r && L<r;i++){
        MinMax(L,R,&k1,&k2);
        if(k1!=-1){
            otg=max(otg,(k1-pre));
            otg=max(otg,(k2-k1));
            pre=k2;
        }
        L+=dul;
        R=min(L+dul-1,r-1);
    }
    return max(otg,(r+1)-pre);
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70