Submission #467660

#	Time	Username	Problem	Language	Result	Execution time	Memory
467660		SirCovidThe19th	Gap (APIO16_gap)	C++17	83.51 / 100	66 ms	1940 KiB

gap

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

#define ll long long

ll findGap(int t, int n){
    ll mn = 1, mx = 1e18, A[n], lim, lb, ans = 0; 
    if (t == 1){
        for (ll i = 0, j = n - 1; i <= j; i++, j--){
            MinMax(mn, mx, &mn, &mx);
            A[i] = mn; A[j] = mx;
            mn++; mx--;
        }
        for (ll i = 1; i < n; i++)
            ans = max(ans, A[i] - A[i - 1]);
    }
    else{
        MinMax(mn, mx, &mn, &mx); 
        lb = (mx - mn) / (n - 1); lim = mx;
        for (ll l = mn, r = mn + lb - 1, prvMx = 1e18; l <= lim; l += lb, r += lb){
            MinMax(l, r, &mn, &mx);
            ans = max(ans, mn - prvMx);
            if (~mx) prvMx = mx; 
        }
    }
    return ans;
}

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