Submission #1107483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107483		evenvalue	Gap (APIO16_gap)	C++17	70 / 100	48 ms	5884 KiB

gap

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

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#define int long long

constexpr int kInf = 1e18;
constexpr int kMod = 1e9 + 7;

pair<int, int> ask(const int l, const int r) {
  int mn, mx;
  MinMax(l, r, &mn, &mx);
  return {mn, mx};
}

int findGap(int32_t T, int32_t n) {
  auto [l, r] = ask(0, kInf);
  if (r - l + 1 == n) return 1;

  const int each = (r - l - 1) / (n - 1);
  const int extra = (r - l - 1) % (n - 1);

  int last = l;
  vector<int> elems = {l};
  for (int i = 1; i <= n - 1; i++) {
    const int len = each + (i <= extra);
    const int a = last + 1;
    const int b = a + len - 1;
    const auto [x, y] = ask(a, b);
    if (x != -1) elems.push_back(x);
    if (y != -1) elems.push_back(y);
    last = b;
  }

  elems.push_back(r);

  int ans = 0;
  for (int i = 1; i < elems.size(); i++) {
    ans = max(ans, elems[i] - elems[i - 1]);
  }

  return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int32_t, int32_t)':
gap.cpp:43:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 1; i < elems.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~

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