Submission #873311

#	Time	Username	Problem	Language	Result	Execution time	Memory
873311		StefanL2005	Gap (APIO16_gap)	C++14	30 / 100	288 ms	3876 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);
        while (start != finish)
       { 
            int p = 0;
            ll a, b;
            MinMax(start + 1, start + (1 << p), &a, &b);
            while (b == -1)
            {
                p++;
                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: 0 / 70