Submission #1214988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214988		kunzaZa183	Gap (APIO16_gap)	C++20	0 / 100	2096 ms	6852 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long findGap(int T, int N) {
  set<ll> si;
  if (T == 1) {
    ll l = 0, r = 1e18;
    while (l <= r) {
      ll a, b;
      MinMax(l, r, &a, &b);

      if (a != -1) si.insert(a);
      if (b != -1) si.insert(b);

      l = a + 1, r = b - 1;
    }

  } else {
    ll mini, maxi;
    MinMax(0, 1e18, &mini, &maxi);

    ll x = (maxi - mini + N - 2) / (N - 1);

    for (int i = mini; i < maxi; i += x) {
      ll a, b;
      MinMax(i, i + x - 1, &a, &b);
      if (a != -1) si.insert(a);
      if (b != -1) si.insert(b);
    }
  }

  vector<ll> vi;
  for (auto a : si) vi.push_back(a);

  ll maxi = 0;
  for (int i = 1; i < N; i++) maxi = max(maxi, vi[i] - vi[i - 1]);

  return maxi;
}

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