제출 #102815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102815		alexpetrescu	Gap (APIO16_gap)	C++14	100 / 100	80 ms	2296 KiB

gap

#include <algorithm>
#include <vector>

#include "gap.h"

long long findGap(int T, int N) {
    long long R = 1000000000000000000LL;
    if (T == 1) {
        long long a = 0, b = R;
        int cnt = 0;
        std::vector < long long > ans;
        while (a <= b && cnt < (N + 1) / 2) {
            cnt++;
            long long x, y;
            MinMax(a, b, &x, &y);
            if (x != -1)
                ans.push_back(x), ans.push_back(y);
            a = x + 1;
            b = y - 1;
        }
        long long sol = 0;
        std::sort(ans.begin(), ans.end());

        for (int i = 1; i < (int)ans.size(); i++)
            sol = std::max(sol, ans[i] - ans[i - 1]);
        return sol;
    }
    long long e, r;
    MinMax(0, R, &e, &r);
    r -= e;
    long long dist = (r + N - 2) / (N - 1), st = e, ans = 0, val = -1;
    for (int i = 1; i < N; i++) {
        long long a, b;
        MinMax(st, st + dist, &a, &b);
        st += dist + 1;

        if (a != -1) {
            if (val != -1)
                ans = std::max(ans, a - val);
            val = b;
        }
    }

    if (N == 2)
        ans = r;

    return ans;
}

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