Submission #36929

#	Time	Username	Problem	Language	Result	Execution time	Memory
36929		imaxblue	Gap (APIO16_gap)	C++14	100 / 100	99 ms	5140 KiB

gap

#include<iostream>
#include "gap.h"
using namespace std;
#define ll long long

int c;
ll b, x, y, pre, lo=0, ans, hi=1000000000000000000LL;
/*void MinMax(ll lo, ll hi, ll *x, ll *y){
    c++;
    if (lo>728704890713443211 || hi<29659227736649406){
        *x=*y=-1;
        return;
    }
    if (lo<=29659227736649406) *x=29659227736649406;
    else *x=728704890713443211;
    if (hi>=728704890713443211) *y=728704890713443211;
    else *y=29659227736649406;
}*/
ll findGap(int t, int n){
    MinMax(lo, hi, &lo, &hi);
    if (t==1){
        if (n<3) return hi-lo;
        for (int l=0; l<(n-1)/2; ++l){
            MinMax(lo+1, max(lo+1, hi-1), &x, &y);
            if (x==-1) break;
            ans=max(ans, max(x-lo, hi-y));
            if (x==y) break;
            if (l==(n-1)/2-1) ans=max(ans, y-x);
            lo=x; hi=y;
        }
        return ans;
    }
    b=(hi-lo+n-2)/n;
    pre=lo; ans=0;
    //cout << lo << ' ' << hi << ' ' << b << endl;
    for (ll l=lo+1; l<hi; l+=b){
        //cout << l << ' ' << endl;
        MinMax(l, min(hi, l+b-1), &x, &y);
        if (x==-1) continue;
        ans=max(ans, x-pre); pre=y;
    }
    ans=max(ans, hi-pre);
    return ans;
}
/*int main(){
    cout << findGap(1, 2) << ' '; cout << c;
    return 0;
}*/

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