Submission #1009645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009645		dpsaveslives	Gap (APIO16_gap)	C++17	30 / 100	46 ms	3536 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18;
ll findGap(int T, int N){
    if(T == 1){
        ll l = 1, r = INF;
        ll mn, mx;
        vector<ll> arr(N);
        int ind = 0;
        for(int i = 1;i<=(N+1)/2;++i){
            MinMax(l,r,&mn,&mx);
            arr[ind] = mn;
            arr[++ind] = mx;
            ++ind;
            l = mn+1; r = mx-1;
        }
        sort(arr.begin(),arr.end());
        ll ans = 0;
        for(int i = 0;i<=arr.size()-1;++i){
            ans = max(ans,arr[i+1]-arr[i]);
        }
        return ans;
    }
    ll a1, an;
    MinMax(1,INF,&a1,&an);
    ll k = (an-a1+N-2)/(N-1); //N-1 differences between i and i+1, I think the N-2 is so that we don't find an immediately?
    ll cur = a1,x,y,ans = k, last = a1;
    while(cur+k <= an){
        MinMax(cur,cur+k,&x,&y); //x >= cur and y <= cur+k
        if(x != -1){ //if there is such a x with x >= cur
            ans = max(ans,x-last);
            last = y; //last really just saves the last one where something was found?
        }
        cur += k+1;
    }
    /*MinMax(cur,an,&x,&y);
    if(x != -1){
        ans = max(ans,x-last);
    }*/
    return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0;i<=arr.size()-1;++i){
      |                       ~^~~~~~~~~~~~~~

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