Submission #539182

#	Time	Username	Problem	Language	Result	Execution time	Memory
539182		timreizin	Gap (APIO16_gap)	C++17	100 / 100	72 ms	3208 KiB

gap

#include "gap.h"
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;

long long findGap(int t, int n)
{
    vector<ll> arr;
    if (t == 1)
    {
        ll a = -1, b = (ll)1e18 + 1;
        for (int i = 0; i < (n + 1) / 2; ++i)
        {
            MinMax(a + 1, b - 1, &a, &b);
            arr.push_back(a);
            arr.push_back(b);
        }
        sort(arr.begin(), arr.end());
    }
    else
    {
        ll a, b;
        MinMax(0, 1e18, &a, &b);
        arr.push_back(a);
        ll x = (b - a + n - 2) / (n - 1);
        for (ll i = a + 1; i < b; i += x)
        {
            ll l, r;
            MinMax(i, i + x - 1, &l, &r);
            if (l != -1)
            {
                arr.push_back(l);
                arr.push_back(r);
            }
        }
        arr.push_back(b);
    }
    ll res = 0;
    for (int i = 0; i + 1 < arr.size(); ++i) res = max(res, arr[i + 1] - arr[i]);
    return res;
}

Compilation message (stderr)

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

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