Submission #110694

#	Time	Username	Problem	Language	Result	Execution time	Memory
110694		baneling100	Gap (APIO16_gap)	C++17	30 / 100	69 ms	1916 KiB

gap

#include "gap.h"
#include <algorithm>
#define MAX_N 100000
#define MAX_A 1000000000000000000

long long A[MAX_N];

long long findGap(int T, int N) {
    
    long long min, max, ans = 0;
    
    if (T == 1) { // subtask 1
        int t = (N + 1) / 2, low = 0, high = N;
        min = -1, max = MAX_A + 1;
        
        for(int i = 0; i < t; i++) {
            MinMax(min + 1, max - 1, &min, &max);        
            A[low++] = min;
            A[--high] = max;
        }
        
        for(int i = 1; i < N; i++)
            if(ans < A[i] - A[i - 1])
                ans = A[i] - A[i - 1];
    }
    else { // subtask 2
        MinMax(0, MAX_A, &min, &max);
        long long gap = (max - min) / N, x, y, done = min, next;
        int M = 0;
        A[M++] = min;
        while(done + 1 < max) {
            x = y = -1;
            next = std::min(done + 1 + gap, max - 1);
            MinMax(done + 1, next, &x, &y);
            if(x != -1) {
                A[M++] = x;
                if(x < y) A[M++] = y;
            }
            done = next;
        }
        A[M++] = max;
        for(int i = 0; i < M; i++)
            if(ans < A[i] - A[i - 1])
                ans = A[i] - A[i - 1];
    }
    
	return ans;
}

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