Submission #464744

#	Time	Username	Problem	Language	Result	Execution time	Memory
464744		nickmet2004	Gap (APIO16_gap)	C++11	83.51 / 100	67 ms	1180 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
#define ll long long
using namespace std;

ll findGap(int T , int n){
    ll x = 0 , y = 1e18 ,mn , mx , ans = 0;
    if(T == 1){
        MinMax(x , y , &mn , &mx);
        x = mn , y = mx;
        for(int i = 1; i < (n + 1) /2; ++i){
            MinMax(x+1 , y-1 , &mn , &mx);
            ans = max({ans, y - mx , mn - x});
            x = mn , y =mx;
        }
    return max(ans , mx-mn);
    }
     //1 2 3 4 5 6
    MinMax(0 , 1e18 , &mn , &mx);
    ll sz = ans = (mx- mn-1) / (n - 1);
    x = mn , y = mx;
    if((x - y + 1) / n == 1)return 1;
    //1  4  6 30
    ll lst = 1e18;
    for(ll i = x; i <= y; i += sz){
        MinMax(i , i + sz , &mn , &mx);
        if(mn == -1)continue;
        ans = max(ans , mn - lst);
        lst = mx;
    }
    return ans;
}

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