Submission #981625

#	Time	Username	Problem	Language	Result	Execution time	Memory
981625		ShauryaTheShep	Gap (APIO16_gap)	C++14	0 / 100	42 ms	3108 KiB

gap

#include <iostream>
#include <climits> // For LONG_LONG_MIN and LONG_LONG_MAX

// Function prototype for provided MinMax function
void MinMax(long long s, long long t, long long* mn, long long* mx);

long long findGap(int T, int N) {
    if (T != 1) {
        // Subtask 1 implementation only
        return -1;
    }

    long long globalMin, globalMax;
    long long mn, mx;
    MinMax(LONG_LONG_MIN, LONG_LONG_MAX, &globalMin, &globalMax);

    if (N == 1) {
        // If there is only one number, no gap exists
        return 0;
    }

    // Calculate the expected maximum number of gaps (N-1)
    long long maxGap = 0;
    long long interval = (globalMax - globalMin) / (N - 1);
    long long prevMax = globalMin;

    for (int i = 1; i < N; ++i) {
        long long lower = globalMin + i * interval;
        long long upper = lower + interval;
        
        MinMax(lower, upper, &mn, &mx);

        if (mn != -1) { // Check if there are numbers in this range
            maxGap = std::max(maxGap, mn - prevMax);
            prevMax = mx;
        }
    }

    // Also check the final gap
    maxGap = std::max(maxGap, globalMax - prevMax);

    return maxGap;
}

// Assume MinMax is implemented correctly as per the problem's environment.
// Typically, this would be something provided in a competitive programming environment.

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