제출 #745189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745189		viwlesxq	Gap (APIO16_gap)	C++17	30 / 100	52 ms	1960 KiB

gap

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

typedef long long ll;

ll Min, Max, s, t;

ll findGap(int T, int N) {
	if (T == 1) {
        s = 0, t = 1e18;
        ll arr[N];
        int l = 0, r = N - 1;
        while (l <= r) {
            MinMax(s, t, &Min, &Max);
            arr[l] = Min, arr[r] = Max;
            s = Min + 1, t = Max - 1;
            l++, --r;
        }
        ll ans = 0;
        for (int i = 1; i < N; ++i) {
            ans = std::max(ans, arr[i] - arr[i - 1]);
        }
        return ans;
    } else {
        s = 0, t = 1e18;
        MinMax(s, t, &Min, &Max);
        ll step = ((Max - Min + 1) + (N - 1)) / (N - 1) - 1;
        ll l = Min, i, x, y, ans = step;
        for (i = Min; i + step < Max; i += step + 1) {
            MinMax(i, i + step, &x, &y);
            if (x != -1) {
                ans = std::max(ans, x - l);
                l = y;
            }
        }
        MinMax(i, Max, &x, &y);
        if (x != -1) {
            ans = std::max(ans, x - l);
        }
        return ans;
    }
}

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