Submission #47946

#	Time	Username	Problem	Language	Result	Execution time	Memory
47946		octopuses	Gap (APIO16_gap)	C++17	0 / 100	78 ms	2300 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 + 1) / (n - 1);
    answer = 0;
    ll pre = a;
    ll l = a;
    ll r = a + gap - 1;

    for(ll i = 0; r < b; ++ i)
    {
      l += gap;
      r += gap;
      l = max(a, l);
      r = min(b, r);
      ll x, y;
      MinMax(l, r, &x, &y);
      if(x == -1)
        continue;
      answer = max(answer, x - pre);
      pre = y;
    }
    return answer;
  }
  int l, r;
  l = -1; 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: 0 / 30
• Subtask 2: 0 / 70