Submission #847044

#	Time	Username	Problem	Language	Result	Execution time	Memory
847044		JooDdae	Gap (APIO16_gap)	C++17	100 / 100	41 ms	3116 KiB

gap

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

ll findGap(int T, int N) {
    ll mn, mx;
    MinMax(0, (ll)1e18, &mn, &mx);
    ll lmn = mn, lmx = mx, ans = 0;

    if(T == 1) {        
        for(int i=1;i<(N+1)/2;i++) {
            MinMax(lmn+1, lmx-1, &mn, &mx);
            ans = max({ans, lmx-mx, mn-lmn});
            lmn = mn, lmx = mx;
        }

        return max(ans, lmx-lmn);
    }

    if(N == 2) return mx-mn;
    ll R = mx;
    ll gap = mx-mn-1;

    ll p = gap / (N-1);
    ll cnt = gap % (N-1);
    lmx = mn;

    for(int i=0;i<N-1;i++) {
        ll r = lmn + p + (i < cnt);
        MinMax(lmn+1, r, &mn, &mx);
        if(mn != -1) ans = max(ans, mn-lmx), lmx = mx;
        lmn = r;
    }
    return max(ans, R-lmx);
}

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