Submission #501367

#	Time	Username	Problem	Language	Result	Execution time	Memory
501367		kevinxiehk	Gap (APIO16_gap)	C++17	100 / 100	63 ms	1844 KiB

gap

#include "gap.h"
// TODO: global variables can be declared here
long long max(long long a, long long b) {
    return (a > b ? a : b);
}
long long findGap(int T, int n) {
    // TODO: implementation
    if(T == 1) {
        long long arr[n + 5];
        for(int i = 0; i < (n + 1) / 2; i++) {
            if(i == 0) MinMax(0, 1000000000000000000LL, &arr[0], &arr[n - 1]);
            else MinMax(arr[i - 1] + 1, arr[n - i] - 1, &arr[i], &arr[n - i - 1]); 
        }
        long long ans = 0;
        for(int i = 0; i < n - 1; i++) ans = max(ans, arr[i + 1] - arr[i]);
        return ans;
    }
    else {
        long long l, r;
        MinMax(0, 1000000000000000000LL, &l, &r);
        long long chunk = (r - l + n - 2) / (n - 1);
        long long a, b, c = l;
        l++;
        long long ans = 0;
        while(l < r) {
            MinMax(l, l + chunk - 1, &a, &b);
            l += chunk;
            if(a == -1) continue;
            ans = max(ans, a - c);
            c = b;
        }
        ans = max(ans, r - c);
        return ans;
    }
}

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