Submission #1009630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009630		dpsaveslives	Gap (APIO16_gap)	C++17	100 / 100	46 ms	3624 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
    ll cur = a1,x,y,ans = k, last = a1;
    while(cur+k+1 <= an){
        MinMax(cur,cur+k,&x,&y);
        if(x != -1){
            ans = max(ans,x-last);
            last = y;
        }
        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: 70 / 70