제출 #383956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383956		mihai145	Gap (APIO16_gap)	C++14	100 / 100	78 ms	2712 KiB

gap

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

const long long INF = 1e18;

long long findGap(int T, int N)
{
    if(T == 2) {
        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;
    }

    std::vector <long long> firstValues, lastValues;
    long long boundL = 0, boundR = INF;
    for(int i = 1; i <= N / 2; i++) {
        long long mn, mx;
        MinMax(boundL, boundR, &mn, &mx);
        firstValues.push_back(mn);
        lastValues.push_back(mx);
        boundL = mn + 1;
        boundR = mx - 1;
    }

    if(N % 2 == 1) {
        long long mn, mx;
        MinMax(boundL, boundR, &mn, &mx);
        firstValues.push_back(mn);
    }

    std::reverse(lastValues.begin(), lastValues.end());

    for(long long val : lastValues) {
        firstValues.push_back(val);
    }

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

    return dif;
}

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