Submission #771027

#	Time	Username	Problem	Language	Result	Execution time	Memory
771027		boris_mihov	Gap (APIO16_gap)	C++17	100 / 100	48 ms	1868 KiB

gap

#include "gap.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;
    
int n;
llong a[MAXN];
llong findGap(int T, int N)
{
    n = N;
    if (T == 1)
    {
        int lPtr = 1;
        int rPtr = n;
        llong lLast = 0;
        llong rLast = 1e18;
        while (lPtr <= rPtr)
        {
            MinMax(lLast, rLast, &lLast, &rLast);
            a[lPtr++] = lLast;
            a[rPtr--] = rLast;
            lLast++; rLast--;
        }

        llong max = 0;
        for (int i = 1 ; i < n ; ++i)
        {
            max = std::max(max, a[i + 1] - a[i]);
        }

        return max;
    }

    llong ans = 1;
    llong min, max;
    MinMax(0, (llong)1e18, &min, &max);
    llong gap = ((max - min + 1) / n + (((max - min + 1) % n) > 0)) * 2 - 1;

    llong last = min;
    while (last < max)
    {
        llong currMin, currMax;
        MinMax(last + 1, last + gap, &currMin, &currMax);
        if (currMin == -1)
        {
            gap *= 2;
            continue;
        }
        
        gap = currMin - last;
        ans = std::max(ans, gap);
        last = currMax;
    }

    return ans;
}

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