Submission #115444

#	Time	Username	Problem	Language	Result	Execution time	Memory
115444		nvmdava	Gap (APIO16_gap)	C++17	100 / 100	73 ms	1968 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
 
long long a[100005];
long long findGap(int T, int N)
{
    if(T == 1){
        a[0] = 0;
        int r = N;
        a[N + 1] = 1000000000000000006;
        for(int l = 1; l <= r; l++){
            MinMax(a[l - 1] + 1, a[r + 1] - 1, &a[l], &a[r]);
            r--;
        }
        long long res = 0;
        for(int l = 1; l < N; l++){
            res = max(res, a[l + 1] - a[l]);
        }
        return res;
    } else {
 
 
    long long s, t;
    MinMax(1, 1000000000000000000, &s, &t);
    long long l, r;
    l = s + 1;
    long long sz = (t - s + 1) / N;
    long long lf = s, res = 0;
    long long a, b;
    while(l < t){
        r = l + sz;
        MinMax(l, r, &a, &b);
        if(a != -1) res = max(res, a - lf);
        if(b != -1) lf = b;
        l = r + 1;
    }
    res = max(res, t - lf);
	return res;
    }
}

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