Submission #1170187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170187		JelalTkm	Gap (APIO16_gap)	C++20	100 / 100	43 ms	2292 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define ll long long

// const int N = 1e6 + 10;
// const int md = 1e9 + 7;
// const int INF = 1e18;

ll findGap(int T, int n) {
  if (T == 1) {
    ll mn, mx;
    vector<ll> a;
    MinMax(0ll, 1e18, &mn, &mx);
    a.push_back(mn); a.push_back(mx);
    while ((int) a.size() < n) {
      mn++, mx--;
      MinMax(mn, mx, &mn, &mx);
      a.push_back(mn), a.push_back(mx);
    }

    sort(a.begin(), a.end());
    ll ans = 0ll;
    for (int i = 1; i < (int) a.size(); i++)
      ans = max(ans, (a[i] - a[i - 1]));

    return ans;
  }
  ll l, r;
  MinMax(0ll, 1e18, &l, &r);
  ll v = (r - l - 3 + n) / (n - 1);
  ll l1 = l, mn, mx, ans = 0ll;
  while (l < r) {
    MinMax(l, min(l + v, r), &mn, &mx);
    if(mn != -1) {
      ans = max(ans, mn - l1);
      l1 = mx;
    }
    l += v + 1;
  }

  return max(ans, r - l1);
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {
    
//   }

//   return 0;
// }

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