Submission #1134939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134939		Hamed_Ghaffari	Gap (APIO16_gap)	C++20	100 / 100	40 ms	2240 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

using ll = long long;

long long findGap(int T, int N) {
  if(T==1) {
    ll l=0, r=1e18;
    vector<ll> vec;
    for(int i=0; i<(N+1)/2; i++) {
      ll mn, mx;
      MinMax(l, r, &mn, &mx);
      vec.push_back(mn);
      vec.push_back(mx);
      l=mn+1, r=mx-1;
    }
    if(vec.size()>N) vec.pop_back();
    sort(vec.begin(), vec.end());
    ll ans=0;
    for(int i=0; i+1<N; i++) ans = max(ans, vec[i+1]-vec[i]);
    return ans;
  }
  else {
    ll mn, mx;
    MinMax(0, 1e18, &mn, &mx);
    ll lb = (mx-mn+N-2)/(N-1);
    ll ans = lb, lst=mn;
    for(ll i=mn; i<=mx; i += lb+1) {
      ll x, y;
      MinMax(i, min(i+lb, mx), &x, &y);
      if(x!=-1) {
        ans = max(ans, x-lst);
        lst = y;
      }
    }
    return ans;
  }
}

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