제출 #467674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467674		SirCovidThe19th	Gap (APIO16_gap)	C++17	30 / 100	76 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 = ceil((mx - mn - 1) / (n - 1.0)) + 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: 0 / 70