Submission #536185

#	Time	Username	Problem	Language	Result	Execution time	Memory
536185		mario05092929	Gap (APIO16_gap)	C++17	100 / 100	64 ms	1872 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
int lp,rp;

long long findGap(int T, int N) {
    ll n = N;
    ll l = 0, r = 1e18,mn,mx;
    if(T == 1) {
        MinMax(l,r,&mn,&mx);
        lp = 1, rp = n;
        while(1) {
            a[lp++] = mn;
            a[rp--] = mx;
            l = mn+1, r = mx-1;
            if(lp > rp) break;
            MinMax(l,r,&mn,&mx);
        }
        ll mxx = 0;
        for(int i = 1;i < n;i++) {
            mxx = max(mxx,a[i+1]-a[i]);
        }
        return mxx;
    }
    else {
        MinMax(l,r,&mn,&mx);
        ll diff = 0;
        ll len = (mx-mn+1)/n+1;
        ll st = mn+1;
        ll tmn,tmx;
        for(int i = 1;i <= n;i++) {
            MinMax(st,st+len-1,&tmn,&tmx);
            st += len;
            if(tmn == -1) continue;
            diff = max(diff,tmn-mn);
            mn = tmx;
        }
        return diff;
    }
}

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