Submission #873709

#	Time	Username	Problem	Language	Result	Execution time	Memory
873709		StefanL2005	Gap (APIO16_gap)	C++14	100 / 100	38 ms	3872 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define ll long long
 
ll findGap(int T, int N)
{
    vector<ll> v(N);
    ll maxDif = 0;

    if (T == 1)
    {
        int p1 = 0, p2 = N - 1;
        ll a = -1, b = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000+ 1;
 
        while (p1 <= p2)
        {
            ll c1, c2;
            MinMax(a + 1, b - 1, &c1, &c2);
            v[p1] = c1;
            v[p2] = c2;
            p1++; p2--;
            a = c1; b = c2;
        }
 
        for (int i = 1; i < N; i++)
            maxDif = max(maxDif, v[i] - v[i - 1]);
    }
    else
    {
        ll start, finish;
        MinMax(0, 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000, &start, &finish);
        maxDif = 1 + (finish - start + 1 - N) / (N - 1); 
        
        while (start != finish)
        { 
            ll p = maxDif;
            ll a, b;

            MinMax(start + 1, start + 1 + p, &a, &b);
            while (b == -1)
            {
                p*=2;
                if (start + 1 + p >= finish)
                    MinMax(start + 1, finish, &a, &b);
                else
                    MinMax(start + 1, start + 1 + p, &a, &b);
            }

            maxDif = max(maxDif, a - start);
            start = b;
        }
    }
    return maxDif;
}

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