Submission #539177

#	Time	Username	Problem	Language	Result	Execution time	Memory
539177		timreizin	Gap (APIO16_gap)	C++17	70 / 100	69 ms	3300 KiB

gap

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

using namespace std;

using ll = long long;

long long findGap(int t, int n)
{
    //[a, b] - n + 1
    //x >= (b - a + 1) / (n - 1)
    ll a, b;
    MinMax(0, 1e18, &a, &b);
    ll x = (b - a + n - 1) / (n - 1);
    vector<ll> arr{a};
    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:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i + 1 < arr.size(); ++i) res = max(res, arr[i + 1] - arr[i]);
      |                     ~~~~~~^~~~~~~~~~~~

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