제출 #351094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351094		ladpro98	Gap (APIO16_gap)	C++14	100 / 100	67 ms	1408 KiB

gap

#include <algorithm> 
#include "gap.h"
#include <iostream>
using namespace std;

const long long MAX_VALUE = 1000000000000000000LL;

long long task1(int n) {
    long long l = -1;
    long long r = MAX_VALUE + 1;
    long long res = 0;
    for (int i = 1; i <= (n + 1) / 2; ++i) {
        long long ll, rr;
        MinMax(l + 1, r - 1, &ll, &rr);
        if (i > 1) {
            res = max(res, ll - l);
            res = max(res, r - rr);
        }
        l = ll;
        r = rr;
    }
    res = max(res, r - l);
    return res;
}

long long task2(int n) {
    long long minimum;
    long long maximum;
    MinMax(0, MAX_VALUE, &minimum, &maximum);
    long long step = (maximum - minimum + n - 2) / (n - 1);
    long long res = step;
    long long last = minimum;
    for (long long v = minimum; v <= maximum; v += step + 1) {
        long long l, r;
        MinMax(v, v + step, &l, &r);
        if (l != -1) {
            res = max(res, l - last);
            last = r;
        }
    }
    return res;
}

long long findGap(int T, int N) {
    return T == 1 ? task1(N) : task2(N);
}

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