제출 #1355593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355593		idkcp	Gap (APIO16_gap)	C++20	100 / 100	27 ms	1972 KiB

gap

/**
 *       author:  Vi Gia Huy
 *    Vi Gia Huy will win VOI 27
**/

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

const long long INF = 1000000000000000000LL;
const int N = 1e5 + 6;
int n;
long long res;

namespace sub1 {
    long long a[N];
    long long mn;
    long long mx;

    void sol() {
        a[0] = -1;
        a[n + 1] = INF + 1;
        int l = 1;
        int r = n;
        while (l <= r) {
            MinMax(a[l - 1] + 1, a[r + 1] - 1, &mn, &mx);
            a[l] = mn;
            a[r] = mx;
            l++;
            r--;
        }
        res = 0;
        for (int i = 1; i < n; i++) {
            res = max(res, a[i + 1] - a[i]);
        }

        return;
    }
}

namespace sub2 {
    long long mn;
    long long mx;

    void sol() {
        MinMax(0, INF, &mn, &mx);

        long long l = (mx - mn + n - 2) / n - 1;
        res = l;
        long long premx = mn;

        for (long long i = mn + 1; i < mx; i += l + 1) {
            long long curmn;
            long long curmx;

            long long tmp = min(i + l, mx - 1);

            MinMax(i, tmp, &curmn, &curmx);

            if (curmn != -1) {
                res = max(res, curmn - premx);
                premx = curmx;
            }
        }

        res = max(res, mx - premx);

        return;
    }
}

long long findGap(int _T, int _N) {
    n = _N;
    if (_T == 1) sub1::sol();
    else sub2::sol();
    return res;
}

• 서브태스크 1: 30 / 30
• 서브태스크 2: 70 / 70