Submission #1160150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160150		kirakaminski968	Gap (APIO16_gap)	C++20	100 / 100	43 ms	1864 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
const ll INF = 1000000000000000001;
ll arr[MAXN];
ll findGap(int T, int N){
    if(T == 1){
        arr[0] = -1; arr[N+1] = INF;
        for(int i = 1;i<=(N+1)/2;++i){
            ll mn,mx; MinMax(arr[i-1]+1,arr[N-i+2]-1,&mn,&mx);
            arr[i] = mn; arr[N-i+1] = mx;
        }
        ll ans = 0;
        for(int i = 1;i<N;++i){
            ans = max(ans,arr[i+1]-arr[i]);
        }
        return ans;
    }
    else{
        ll mn,mx;
        MinMax(0,INF,&mn,&mx);
        ll b = (mx-mn)/(N-1);
        if((mx-mn)%(N-1) != 0) ++b;
        ll ans = 0;
        ll last = mn;
        for(ll cur = mn;cur < mx;cur += b){
            ll x = min(cur+b-1,mx-1);
            ll curmn, curmx; MinMax(cur,x,&curmn,&curmx);
            ans = max(ans,curmn-last);
            if(curmx > 0) last = curmx;
        }
        ans = max(ans,mx-last);
        return ans;
    }
}

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