Submission #981634

#	Time	Username	Problem	Language	Result	Execution time	Memory
981634		ShauryaTheShep	Gap (APIO16_gap)	C++14	0 / 100	40 ms	3100 KiB

gap

#include <iostream>
#include <climits>
#include <vector>
 
// 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) {
        // Only implementing subtask 1
        return -1;
    }

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

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

    // Calculate optimal number of segments
    long long segmentSize = (globalMax - globalMin) / (N - 1);
    long long maxGap = 0;
    long long lastMax = globalMin;

    // Process each segment to find the largest gap
    for (long long i = 0; i < N - 1; ++i) {
        long long s = globalMin + i * segmentSize + 1;  // Start of the next segment
        long long t = s + segmentSize - 1;             // End of the next segment
        if (i == N - 2) t = globalMax;                // Ensure the last segment reaches globalMax

        long long mn, mx;
        MinMax(s, t, &mn, &mx);

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

    return maxGap;
}

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