제출 #536394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536394		qwerasdfzxcl	Gap (APIO16_gap)	C++14	100 / 100	66 ms	1188 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll ans;

ll findGap(int T, int N){
    if (T==1){
        ll L, R, ans = 0;
        MinMax(0, (ll)1e18, &L, &R);
        int cnt = 1;
        while(true){
            ll nL, nR;
            if (L+1<=R-1 && cnt < (N+1)/2) MinMax(L+1, R-1, &nL, &nR);
          	else nL = -1;
            if (nL==-1) {ans = max(ans, R - L); return ans;}
            ans = max(ans, max(nL - L, R - nR));
            L = nL, R = nR;
            cnt++;
        }
    }
    ll L, R;
    MinMax(0, (ll)1e18, &L, &R);

    ll len = R - L;
    ll Bsz = len / (N-1);
    ans = Bsz;

    ll prv = -1;
    for (ll i=L;i<=R;i+=Bsz+1){
        ll tL, tR;
        MinMax(i, i+Bsz, &tL, &tR);
        if (tL!=-1 && prv!=-1) ans = max(ans, tL - prv);
        if (tR!=-1) prv = tR;
    }
    return ans;
}

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