Submission #467688

#	Time	Username	Problem	Language	Result	Execution time	Memory
467688		SirCovidThe19th	Gap (APIO16_gap)	C++17	100 / 100	66 ms	1944 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 - 2) / (n - 1); lim = mx;
        for (ll l = mn + 1, r = l + lb - 1, prvMx = mn; l <= lim; l += lb, r += lb){
            if (l == lim) mn = l; else MinMax(l, r, &mn, &mx);
            ans = max(ans, mn - prvMx);
            if (~mx) prvMx = mx; 
        }
    }
    return ans;
}

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