Submission #119109

#	Time	Username	Problem	Language	Result	Execution time	Memory
119109		Charis02	Gap (APIO16_gap)	C++14	100 / 100	54 ms	2040 KiB

gap

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include "gap.h"
#define ll long long
#define MAXV 1e18

using namespace std;
long long solve1(int n)
{
    ll ar[n];

    ll curl = 1;
    ll curh = n-2;
    MinMax(0,MAXV,&ar[0],&ar[n-1]);

    while(curl <= curh)
    {
        MinMax(ar[curl-1]+1,ar[curh+1]-1,&ar[curl],&ar[curh]);
        curl++;
        curh--;
    }

    ll dif = 0;

    for(int i = 1;i < n;i++)
    {
        dif = max(dif,ar[i]-ar[i-1]);
    }

    return dif;
}

long long findGap(int T, int N)
{
    if(T == 1)
        return solve1(N);

    long long a,b;
    MinMax(0LL,MAXV,&a,&b);
    ll dif = (b-a)/(N-1)-2;
    ll k = 1;

    while(a < b)
    {
        ll w,x;
        MinMax(a+1,a+dif*k,&x,&w);

        if(w == -1)
        {
            k++;
            continue;
        }

        if(k != 1)
            dif = max(dif,x-a);

        k=1;
        a = w;
    }

    return dif;
}

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