Submission #97728

#	Time	Username	Problem	Language	Result	Execution time	Memory
97728		dalgerok	Gap (APIO16_gap)	C++17	100 / 100	98 ms	4088 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
using namespace std;


long long a[400005];

long long findGap(int T, int N){
    long long mn, mx, l = 0, r = 1e18, ans = 0;
    int sz = 0;
    if(T == 1){
        int tl = 1, tr = N;
        while(tl <= tr){
            MinMax(l, r, &mn, &mx);
            a[tl++] = mn;
            a[tr--] = mx;
            l = mn + 1;
            r = mx - 1;
        }
        sz = N;
    }
    else{
        MinMax(l, r, &mn, &mx);
        long long shift = (mx + mn + N - 1) / N, xx, yy;
        a[++sz] = mn;
        l = mn + 1;
        r = l + shift;
        while(l < mx){
            MinMax(l, min(r, mx - 1), &xx, &yy);
            if(xx != -1){
                a[++sz] = xx;
                a[++sz] = yy;
            }
            l = r + 1;
            r = l + shift;
        }
        a[++sz] = mx;
    }
    for(int i = 2; i <= sz; i++){
        ans = max(ans, a[i] - a[i - 1]);
    }
    return ans;
}

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