Submission #360305

#	Time	Username	Problem	Language	Result	Execution time	Memory
360305		joylintp	Gap (APIO16_gap)	C++17	100 / 100	65 ms	3296 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;

long long findGap(int T, int N)
{
    long long l, r;
    MinMax(0, 1000000000000000000, &l, &r);

    if (N == 2)
        return r - l;

    if (T == 1)
    {
        vector<long long> a(N);
        a[0] = l, a[N - 1] = r;

        for (int i = 1; i <= N - i - 1; i++)
            MinMax(a[i - 1] + 1, a[N - i] - 1, &a[i], &a[N - i - 1]);

        long long mx = 0;
        for (int i = 0; i + 1 < N; i++)
            mx = max(mx, a[i + 1] - a[i]);
        return mx;
    }
    else
    {
        long long ma = (r - l - N - 1) / (N - 1) + !!((r - l - N - 1) % (N - 1)) + 1;

        long long x, y;
        vector<long long> a = {l};
        for (long long i = l + 1; i < r; i += ma + 1)
        {
            MinMax(i, min(r - 1, i + ma), &x, &y);
            if (x != -1)
                a.push_back(x), a.push_back(y);
        }
        a.push_back(r);

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

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:41:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i + 1 < a.size(); i++)
      |                         ~~~~~~^~~~~~~~~~

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