Submission #1153414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153414		AlgorithmWarrior	Gap (APIO16_gap)	C++20	30 / 100	44 ms	3384 KiB

gap

#include <bits/stdc++.h>

using namespace std;

#include "gap.h"

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

long long findGap(int T, int N){
    long long st,dr;
    MinMax(0,1e18,&st,&dr);

    if(T==1){
        long long answer=1;
        int i;
        for(i=1;i<=(N-1)/2;++i){
            long long ultst=st;
            long long ultdr=dr;
            MinMax(ultst+1,ultdr-1,&st,&dr);
            maxself(answer,st-ultst);
            maxself(answer,ultdr-dr);
        }
        maxself(answer,dr-st);
        return answer;
    }

    long long answer=(dr-st+N-2)/(N-1);
    vector<long long>v;
    v.push_back(st);
    long long i;
    for(i=st+1;i<dr;i+=answer+1){
        long long mn,mx;
        MinMax(i,i+answer,&mn,&mx);
        if(st!=-1){
            v.push_back(mn);
            v.push_back(mx);
        }
    }
    if(i==dr)
        v.push_back(dr);
    for(i=0;i<(int)v.size()-1;++i)
        maxself(answer,v[i+1]-v[i]);
    return answer;
}

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