Submission #383955

#	Time	Username	Problem	Language	Result	Execution time	Memory
383955		mihai145	Gap (APIO16_gap)	C++14	70 / 100	74 ms	2276 KiB

gap

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

const long long INF = 1e18;

long long findGap(int T, int N)
{
    long long a0, aN;
    MinMax(0LL, INF, &a0, &aN);
    long long L = (aN - a0) / (N - 1);

    if(N == 2) {
        return L;
    }
    if((aN - a0) % (N - 1) != 0) {
        ++L;
    }

    std::vector <long long> values;
    values.push_back(a0);

    long long prevRightEnd = a0;
    for(int i = 1; i <= N - 1; i++) {
        long long mn, mx;
        if(prevRightEnd + L - 1 < aN) {
            MinMax(prevRightEnd + 1, prevRightEnd + L, &mn, &mx);
        } else {
            if(prevRightEnd + 1 <= aN - 1) {
                MinMax(prevRightEnd + 1, aN - 1, &mn, &mx);
            }
        }
        prevRightEnd = prevRightEnd + L;

        if(mn != -1) {
            values.push_back(mn);
            if(mx != mn) {
                values.push_back(mx);
            }
        }
    }
    values.push_back(aN);

    long long dif = 0;
    for(int i = 1; i < (int)values.size(); i++) {
        dif = std::max(dif, values[i] - values[i - 1]);
    }

	return dif;
}

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