oj.uz

Submission #396220

# Submission time Handle Problem Language Result Execution time Memory
396220 2021-04-29T14:57:42 Z Cyanmond Gap (APIO16_gap) C++17
100 / 100
 65 ms 1956 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 11 ms 712 KB Output is correct
17 Correct 11 ms 584 KB Output is correct
18 Correct 12 ms 712 KB Output is correct
19 Correct 12 ms 712 KB Output is correct
20 Correct 9 ms 584 KB Output is correct
21 Correct 48 ms 1812 KB Output is correct
22 Correct 48 ms 1784 KB Output is correct
23 Correct 43 ms 1900 KB Output is correct
24 Correct 49 ms 1864 KB Output is correct
25 Correct 37 ms 1800 KB Output is correct
26 Correct 44 ms 1956 KB Output is correct
27 Correct 43 ms 1856 KB Output is correct
28 Correct 43 ms 1788 KB Output is correct
29 Correct 52 ms 1812 KB Output is correct
30 Correct 35 ms 1808 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 1 ms 200 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 16 ms 456 KB Output is correct
17 Correct 16 ms 456 KB Output is correct
18 Correct 16 ms 468 KB Output is correct
19 Correct 15 ms 476 KB Output is correct
20 Correct 7 ms 456 KB Output is correct
21 Correct 60 ms 1072 KB Output is correct
22 Correct 61 ms 964 KB Output is correct
23 Correct 64 ms 1044 KB Output is correct
24 Correct 65 ms 1052 KB Output is correct
25 Correct 55 ms 1084 KB Output is correct
26 Correct 61 ms 1036 KB Output is correct
27 Correct 60 ms 1036 KB Output is correct
28 Correct 60 ms 1044 KB Output is correct
29 Correct 59 ms 1076 KB Output is correct
30 Correct 32 ms 1020 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 1 ms 200 KB Output is correct