Submission #95631

#	Time	Username	Problem	Language	Result	Execution time	Memory
95631		SomeoneUnknown	Gap (APIO16_gap)	C++14	70 / 100	61 ms	1272 KiB

gap

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

long long findGap(int T, int N)
{
    //MinMax(3,5,*l,*h)
    if(T == 1){
        long long pl, ph, nl, nh;
        MinMax(0,1000000000000000000, &pl, &ph);
        long long best = 0;
        for(int i = 1; i < (N+1)/2; i++){
            MinMax(pl+1, ph-1, &nl,&nh);
            best = max(ph-nh, best);
            best = min(nl-pl, best);
        }
        return best;
    }else{
        long long best = 0;
        long long mx, mn;
        MinMax(0, 1000000000000000000, &mn, &mx);

        long long cur = mn;
        long long interval = (mx-mn-1)/(N-1)+1;
        for(long long a = mn+1; a < mx; a += interval){
            long long l, h;
            MinMax(a, min(a + interval-1, mx-1), &l, &h);
            if(l != -1){
                best = max(best, l-cur);
                cur = h;
            }
        }//*/
        best = max(best, mx-cur);
        return best;
    }
}
/*
#include <bits/stdc++.h>
using namespace std;

long long findGap(int T, long long N){
    //MinMax(3,5,*l,*h)
    if(T == 1){
        int pl, ph, nl, nh;
        MinMax(0,1000000000000000000, *pl, *ph);
        int best = 0;
        for(int i = 1; i < (N+1)/2; i++){
            MinMax(pl+1, ph-1, *nl, *nh);
            best = max(ph-nh, best);
            best = min(nl-pl, best);
        }
        return best;
    }
}

*/

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