Submission #1325251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325251		riafhasan2010	Gap (APIO16_gap)	C++17	100 / 100	53 ms	2288 KiB

gap

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

long long findGap(int t, int n) {
  if (t == 1) {
    ll mn = -1, mx = 1e18 + 1, l = 0, r = 1e18, ans = 0;
    vector<ll> a;
    for (int i = 1; i <= (n + 1) / 2; i++) {
      MinMax(l, r, &mn, &mx);
      if (mn < 0 or mx < 0) break;
      l = mn + 1;
      r = mx - 1;
      a.push_back(mn);
      a.push_back(mx);
    }
    sort(a.begin(), a.end());
    int len = a.size();
    for (int i = 1; i < len; i++) {
      ans = max(ans, a[i] - a[i - 1]);
    }
    return ans;
  }
  else {
    ll first, last, l = 0, ans = 0;
    MinMax(l, 1e18, &first, &last);
    ll dif = (last - first + n - 2) / (n - 1);
    ans = dif; l = first;
    for (ll i = l + 1; i < last; i += dif + 1) {
      ll mn, mx;
      MinMax(i, min(i + dif, last - 1), &mn, &mx);
      if (mn == -1) continue;
      ans = max(ans, mn - l);
      l = mx;
    }
    ans = max(ans, last - l);
    return ans;
  }
}

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