Submission #764402

#	Time	Username	Problem	Language	Result	Execution time	Memory
764402		Ahmed57	Gap (APIO16_gap)	C++17	100 / 100	38 ms	1112 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long INF = 1e18;
long long findGap(int T,int N){
    long long mn ,mx;
    MinMax(0,INF,&mn,&mx);
    if(N==2)return (mx-mn);
    if(T==1){
        long long all= 0;
        for(int i = 0;i<(N-1)/2;i++){
            long long mn2 , mx2;
            MinMax(mn+1,mx-1,&mn2,&mx2);
            all = max(all,mn2-mn);
            all = max(all,mx-mx2);
            swap(mn,mn2);swap(mx,mx2);
        }
        all = max(all,mx-mn);
        return all;
    }
    long long diff = (mx-mn+(N-1))/N;
    long long ans = diff;
    long long start = mn;
    long long la = mn;
    while(start<mx){
        long long l = start+1 , r = start+ans+1;
        long long mn2 , mx2 ;
        MinMax(l,r,&mn2,&mx2);
        if(mn2!=-1){
            ans = max(ans,mn2-la);
            la = mx2;
            start = mx2;
        }else{
            start+=ans;
        }
    }
    return ans;
}

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