| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 396202 | Cyanmond | Gap (APIO16_gap) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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>
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);
}
#endif
// solve
llint solve_case1(int N) {
// T = 1
std::vector<llint> A(N);
llint L = -1, R = 1ll << 62;
int cnt = 0;
while (cnt < ((N + 1) >> 1)) {
llint nxL, nxR;
MinMax(L, R, nxL, nxR);
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;
}
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;
MinMax(L, R, nxL, nxR);
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;
}
if (T == 2) {
// yet...
return 0ll;
}
}