제출 #718997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718997		nguyentunglam	Gap (APIO16_gap)	C++17	70 / 100	65 ms	1864 KiB

gap

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#include "gap.h"
long long a[N];
long long findGap(int T, int n) {
    long long mn, mx;
    if (T == 1) {
        mn = -1; mx = 1e18 + 1;
        for(int i = 1; i <= (n + 1) / 2; i++) {
            MinMax(mn + 1, mx - 1, &mn, &mx);
            a[i] = mn; a[n - i + 1] = mx;
        }

        long long res = 0;
        for(int i = 2; i <= n; i++) res = max(res, a[i] - a[i - 1]);
        return res;
    }

    MinMax(0, 1e18, &mn, &mx);

    long long delta = (mx - mn) / (n - 1) + ((mx - mn)  % (n - 1) > 0);
    long long s = mn + 1, last = mn;
    long long res = delta, lmt = mx - 1;
    long long a = 1e18, b = 0, c = mn, d = mx;

    while (s <= lmt) {
        long long t = min(lmt, s + delta);
        MinMax(s, t, &mn, &mx);

        if (mn != -1) {
            a = min(a, mn); b = max(b, mx);

            res = max(res, mn - last);
            last = mx;
        }
        s = t + 1;
    }

    if (a == 1e18) res = max(res, d - c);
    else res = max(res, a - c), res = max(res, d - b);

    return res;
}

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