Submission #21905

#	Time	Username	Problem	Language	Result	Execution time	Memory
21905		mohammad_kilani	Gap (APIO16_gap)	C++14	100 / 100	143 ms	12420 KiB

gap

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

map<long long,bool> vis;
vector<long long> v;

long long findGap(int T, int N)
{   long long ans = 0;
    if(T == 1){
        long long mn=0,mx=0;
        long long s = 0 , e = 1e18;
        for(int i=0;i<(N+1)/2;i++){
            MinMax(s,e,&mn,&mx);
            if(!vis[mn])
            v.push_back(mn);
            vis[mn] = true;
            if(!vis[mx])
            v.push_back(mx);
            vis[mx] = 1;
            s = mn+1;
            e = mx-1;
        }
        sort(v.begin(),v.end());
        int si = v.size();
        for(int i=0;i<si-1;i++){
            ans = max(ans,v[i+1]-v[i]);
        }
    }
    else{
        long long s,e;
        MinMax(0,1e18,&s,&e);
        long long step = (e-s)/(N-1);
        ans = step;
        long long mn,mx;
        for(long long i = s+step+1;i<e;){
            for(;i<e;i+=step){
                MinMax(s+1,i,&mn,&mx);
                if(mx != -1)
                    break;
            }
            long long f = mx;
            if(i >= e){
                f = e;
                MinMax(i-step,f,&mn,&mx);
                ans = max(ans,mn-s);
                step = ans;
            }
            else{
                ans = max(ans,mn-s);
                step = ans;
            }
            s = f;
            i = s + step+1;
        }
    }
    return ans;
}

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