Submission #849860

#	Time	Username	Problem	Language	Result	Execution time	Memory
849860		nnin	Gap (APIO16_gap)	C++14	100 / 100	41 ms	3108 KiB

gap

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

long long findGap(int T, int N) {
    ll mn, mx, curmn, curmx;
    MinMax((ll)0, (ll)1e18, &mn, &mx);
    ll ans = 0;
    if(T==1) {
        while(N>2) {
            MinMax(mn+1, mx-1, &curmn, &curmx);
            ans = max(ans,  max(curmn-mn, mx-curmx));
            N -= 2;
            mx = curmx;
            mn = curmn;
        }
        ans = max(ans, mx-mn);
    } else {
        ll gap = ans = (mx-mn-1)/(N-1);
        ll rem = (mx-mn-1)%(N-1);
        ll last = mn;
        for(int i=1;i<N;i++) {
            MinMax(last+1, mn+gap+(i<=rem), &curmn, &curmx);
            if(curmn!=-1) {
                ans = max(ans, curmn-last);
                last = curmx;
            }
            mn += gap+(i<=rem);
        }
        ans = max(ans, mx-last);
    }
    return ans;
}

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