Submission #84387

#	Time	Username	Problem	Language	Result	Execution time	Memory
84387		Alexa2001	Gap (APIO16_gap)	C++17	100 / 100	102 ms	3564 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll lim = 1e18;

long long findGap(int T, int N)
{
    ll *A, *B;
    ll ans = 0;
    A = new ll(); B = new ll();

    if(T == 1)
    {
        ll x = 0, y = lim;
        int i;
        for(i=0; i<(N+1)/2; ++i)
        {
            MinMax(x, y, A, B);
            if(i)
            {
                ans = max(ans, *A - x + 1);
                ans = max(ans, y - *B + 1);
            }
            x = *A + 1;
            y = *B - 1;
        }
        if(N%2==0) ans = max(ans, y-x+2);
        return ans;
    }

    MinMax(0, lim, A, B);
    ll X, Y;
    X = *A, Y = *B;

    ll i, S = (Y-X) / (N-1) + 1;
    vector<ll> endpoints;

    for(i = 0; i <= Y-X; i += S)
    {
        MinMax(X+i, X + min(i+S-1, Y-X), A, B);
        if(*A == -1) continue;
        endpoints.push_back(*A);
        endpoints.push_back(*B);
    }
    endpoints.push_back(Y);

    int j;
    for(j=0; j<endpoints.size()-1; ++j)
        ans = max(ans, endpoints[j+1] - endpoints[j]);
    return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0; j<endpoints.size()-1; ++j)
              ~^~~~~~~~~~~~~~~~~~~

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