Submission #47960

#	Time	Username	Problem	Language	Result	Execution time	Memory
47960		octopuses	Gap (APIO16_gap)	C++17	89.04 / 100	86 ms	2124 KiB

gap

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

#define ll long long
#define M (ll)(1e18)

using namespace std;
ll _A[100020];

long long findGap(int T, int n)
{
  if(T == 2)
  {
    ll a, b, answer;
    MinMax(0, M, &a, &b);
    ll gap = (b - a) / (n - 1);
    answer = gap - 1;
    ll pre = a;
    ll l = a - gap + 1;
    ll r = a;

    for(ll i = 0; r + 1 < b; ++ i)
    {
      l += gap;
      r += gap;
      r = min(b - 1, r);
      ll x, y;
      if(l > r)
      {
        break;
      }
      MinMax(l, r, &x, &y);
      if(x == -1)
        continue;
      answer = max(answer, x - pre);
      pre = y;
    }
    answer = max(b - pre, answer);
    return answer;
  }
  int l, r;
  _A[0] = -1;
  l = 0; r = n + 1;
  _A[r] = M + 1;
  l ++; r --;
  while(l <= r)
  {
    MinMax(_A[l - 1] + 1, _A[r + 1] - 1, &_A[l], &_A[r]);
    l ++;
    r --;
  }
  ll answer = 0;
  for(int i = 2; i <= n; ++ i)
    answer = max(answer, _A[i] - _A[i - 1]);
  return answer;
}

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