Submission #396220

#	Time	Username	Problem	Language	Result	Execution time	Memory
396220		Cyanmond	Gap (APIO16_gap)	C++17	100 / 100	65 ms	1956 KiB

gap

#include "bits/stdc++.h"
#pragma region template
using llint = long long;
using isize = std::ptrdiff_t;
using usize = std::size_t;

template <class T>
[[nodiscard]] inline T read() {
  T ret;
  std::cin >> ret;
  return ret;
}

template <class T>
constexpr T floordiv(const T dividend, const T divisor) {
  return (dividend + divisor - 1) / divisor;
}

template <class T>
auto mk_vec(const int n, const T value) {
  return std::vector(n, value);
}
template <class... Args>
auto mk_vec(const int n, Args... args) {
  return std::vector(n, mk_vec(args...));
}

template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class range {
  struct range_iterator {
    T itr;
    constexpr range_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const range_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };

 public:
  constexpr range(const T first_, const T last_) noexcept
      : first(first_), last(last_) {}
  constexpr range_iterator begin() const noexcept { return first; }
  constexpr range_iterator end() const noexcept { return last; }

 private:
  const range_iterator first, last;
};

template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class revrange {
  struct revrange_iterator {
    T itr;
    constexpr revrange_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { --itr; }
    constexpr bool operator!=(const revrange_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };

 public:
  constexpr revrange(const T first_, const T last_) noexcept
      : first(first_), last(last_ - 1) {}
  constexpr revrange_iterator begin() const noexcept { return first; }
  constexpr revrange_iterator end() const noexcept { return last; }

 private:
  const revrange_iterator first, last;
};

template <class F>
class rec_lambda {
 public:
  constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }

 private:
  F f;
};
#pragma endregion

#ifdef _MSC_VER
// Sample program
constexpr std::array<llint, 4> sample = {2, 3, 6, 8};
constexpr int sampleN = 4;
void MinMax(llint s, llint t, llint& mn, llint& mx) {
  const auto itr1 = std::lower_bound(sample.begin(), sample.end(), s);
  const auto itr2 = std::upper_bound(sample.begin(), sample.end(), t);
  if (itr1 == sample.end() or itr2 == sample.begin() or itr1 == itr2) {
    mn = mx = -1;
    return;
  }
  mn = *itr1;
  mx = *(itr2 - 1);
}
#else
#include "gap.h"
#endif

llint findGap(int T, int N) {
  /*
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  */
  if (T == 1) {
    // T = 1
    std::vector<llint> A(N);
    llint L = -1, R = 1ll << 62;
    int cnt = 0;
    while (cnt < ((N + 1) >> 1)) {
      llint nxL, nxR;
#ifdef _MSC_VER
      MinMax(L, R, nxL, nxR);
#else
      MinMax(L, R, &nxL, &nxR);
#endif
      if (nxL == -1 and nxR == -1) continue;
      A[cnt] = nxL;
      A[N - cnt - 1] = nxR;
      ++cnt;
      L = ++nxL;
      R = --nxR;
    }
    llint answer = 0;
    for (int i : range(0, N - 1))
      if (answer < A[i + 1] - A[i]) answer = A[i + 1] - A[i];
    return answer;
  } else {
    llint L = -1, R = 1ll << 62;
#ifdef _MSC_VER
    MinMax(L, R, L, R);
#else
    MinMax(L, R, &L, &R);
#endif
    llint min_width = (R - L) / N + ((R - L) % N == 0 ? 0 : 1);
    // answer >= min_width
    llint lastx = L;
    llint ans = 0ll;
    for (llint mn = L + 1, mx = L + min_width, cnt = 0; cnt < N;
         mn += min_width, mx += min_width, ++cnt) {
      llint mnr, mxr;
#ifdef _MSC_VER
      MinMax(mn, mx, mnr, mxr);
#else
      MinMax(mn, mx, &mnr, &mxr);
#endif
      if (mnr == -1 and mxr == -1) continue;
      if (ans < mnr - lastx) ans = mnr - lastx;
      lastx = mxr;
    }
    if (ans < R - lastx) ans = R - lastx;
    return ans;
  }
}

Compilation message (stderr)

gap.cpp:2: warning: ignoring #pragma region template [-Wunknown-pragmas]
    2 | #pragma region template
      | 
gap.cpp:84: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
   84 | #pragma endregion
      |

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