Submission #47940

#	Time	Username	Problem	Language	Result	Execution time	Memory
47940		octopuses	Gap (APIO16_gap)	C++17	0 / 100	89 ms	2176 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 = 0; r = n + 1;
  _A[r] = M;
  l ++; r ++;
  while(l <= r)
  {
    MinMax(_A[l - 1], _A[r + 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