Submission #72942755
Source Code Expand
#define FULL_LIB 1
#define CODETEST 0
#define OPTUNE 0
#define PERFORMANCE 0
#define EVAL 0
#define UNIT_TEST 0
#define TIME_LIMIT (1950)
#define NOT_SUBMIT 0
#define VALIDATION 0
#define IO_FILE 0
#define SELF_JUDGE 0
#define OUTPUT_INFO 0
#define OUTPUT_FINAL_INFO 0
#define OUTPUT_LOG 0
#define OUTPUT_VISUAL 0
#define OUTPUT_PERF 0
#define OUTPUT_COMMENT 0
#define FIX_RESULT 0
#define FIX_LOOP_COUNT 80000
#define TIME_LIMIT_US (TIME_LIMIT * 1000)
#define OUT_INFO OUTPUT_INFO
#define OUT_LOG OUTPUT_LOG
#define OUT_VIS OUTPUT_VISUAL
#define OUT_PERF OUTPUT_PERF
#ifdef __clang_version__
#pragma clang diagnostic ignored "-Wunknown-pragmas"
#pragma clang diagnostic ignored "-Wunknown-warning-option"
#pragma clang diagnostic ignored "-Wmissing-braces"
#endif
#ifndef _MSC_VER
#pragma GCC target("avx512f,avx512bw,avx512dq,avx512vl,fma,prefer-vector-width=512")
#pragma GCC optimize("O3,unroll-loops,omit-frame-pointer")
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-function"
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
#endif
#define _USE_MATH_DEFINES
#ifdef __clang_version__
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cfenv>
#include <cinttypes>
#include <cstdint>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <optional>
#else
#include <bits/stdc++.h>
#endif
using namespace std;
#define FOR(i, s, e) for (int i = int(s), i##_end = int(e); i < i##_end; ++i)
#define RFOR(i, s, e) for (int i = int(e) - 1, i##_s = int(s); i >= i##_s; --i)
#define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)
#define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
template <class T, class U>
inline void chmin(T& a, const U& b) {
if (b < a) {
a = b;
}
}
template <class T, class U>
inline void chmax(T& a, const U& b) {
if (a < b) {
a = b;
}
}
template <class T, class U, class V>
inline void chclip(T& v, const U& lower, const V& upper) {
if (v < lower) {
v = lower;
}
else if (v > upper) {
v = upper;
}
}
template <class T>
inline constexpr T square(T v) {
return v * v;
}
template <class T, int SIZE>
constexpr int len(const T (&)[SIZE]) {
return SIZE;
}
#define cauto const auto
#include <cstdint>
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using s8 = int8_t;
using s16 = int16_t;
using s32 = int32_t;
using s64 = int64_t;
using f32 = float;
using f64 = double;
using Clock = chrono::high_resolution_clock;
using TimePoint = Clock::time_point;
struct ChronoTimer {
private:
TimePoint startTime_;
TimePoint endTime_;
public:
void Init() {
startTime_ = Clock::now();
endTime_ = startTime_;
}
void Start(int limit) {
endTime_ = startTime_ + chrono::milliseconds(limit);
}
int ElapseTimeMs() const {
return (int)chrono::duration_cast<chrono::milliseconds>(Clock::now() - startTime_).count();
}
bool IsOver() const {
return Clock::now() >= endTime_;
}
inline void StartMs(int limit) {
endTime_ = startTime_ + chrono::milliseconds(limit);
}
inline void StartUs(int limit) {
endTime_ = startTime_ + chrono::microseconds(limit);
}
inline void Join() {
}
inline int ElapseTimeUs() const {
return (int)chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - startTime_)
.count();
}
void SetElapseTimeMs(int ms) {
auto now = chrono::high_resolution_clock::now();
auto limit = endTime_ - startTime_;
startTime_ = now - chrono::milliseconds(ms);
endTime_ = startTime_ + limit;
}
inline int LeftToUS(const TimePoint& limit) const {
return (int)chrono::duration_cast<chrono::microseconds>(limit - chrono::high_resolution_clock::now()).count();
}
inline double NowRate() const {
return (chrono::high_resolution_clock::now() - startTime_).count() / (double)(endTime_ - startTime_).count();
}
inline double CalcRate(const TimePoint& start) const {
return (chrono::high_resolution_clock::now() - start).count() / (double)(endTime_ - start).count();
}
inline TimePoint Now() const {
return chrono::high_resolution_clock::now();
}
inline TimePoint StartTime() const {
return startTime_;
}
inline TimePoint EndTime() const {
return endTime_;
}
TimePoint GetLimitTimePointUs(int limit) const {
return startTime_ + chrono::microseconds(limit);
}
};
TimePoint Now() {
return chrono::high_resolution_clock::now();
}
ChronoTimer timer_;
template <class T>
void InstanceRun(int argc, const char* argv[]) {
timer_.Init();
T* m = new T;
m->Run(argc, argv);
quick_exit(0);
}
struct Main;
signed main(int argc, const char* argv[]) {
cin.tie(0);
ios::sync_with_stdio(0);
InstanceRun<Main>(argc, argv);
}
struct MemoryException {};
#define VABORT()
#define VASSERT(exp)
template <class A, class B>
struct pr {
union {
A a;
A x;
A first;
};
union {
B b;
B y;
B second;
};
bool operator==(pr const& r) const {
return a == r.a && b == r.b;
}
bool operator!=(pr const& r) const {
return !((*this) == r);
}
bool operator<(pr const& r) const {
if (a == r.a) {
return b < r.b;
}
return a < r.a;
}
bool operator>(pr const& r) const {
return r < (*this);
}
pr& operator+=(pr const& v) {
a += v.a;
b += v.b;
return *this;
}
pr& operator-=(pr const& v) {
a -= v.a;
b -= v.b;
return *this;
}
template <class C, class D>
auto operator+(pr<C, D> const& v) const {
return pr<decltype(a + v.a), decltype(b + v.b)>{a + v.a, b + v.b};
}
template <class C, class D>
auto operator-(pr<C, D> const& v) const {
return pr<decltype(a - v.a), decltype(b - v.b)>{a - v.a, b - v.b};
}
template <class C, class D>
explicit operator pr<C, D>() const {
return {C(a), D(b)};
}
template <class T>
auto operator*(T const& v) const -> pr<decltype(x * v), decltype(y * v)> {
return {x * v, y * v};
}
template <class T>
auto operator/(T const& v) const -> pr<decltype(x / v), decltype(y / v)> {
return {x / v, y / v};
}
template <class T>
pr& operator*=(T const& v) {
x *= v;
y *= v;
return *this;
}
template <class T>
pr& operator/=(T const& v) {
x /= v;
y /= v;
return *this;
}
pr operator-() const {
return pr{-x, -y};
}
void flip() {
swap(x, y);
}
friend istream& operator>>(istream& is, pr& p) {
is >> p.a >> p.b;
return is;
}
friend ostream& operator<<(ostream& os, pr const& p) {
os << p.a << " " << p.b;
return os;
}
template <size_t I>
auto get() const {
if constexpr (I == 0) {
return x;
}
else if constexpr (I == 1) {
return y;
}
}
};
using pint = pr<int, int>;
using pdouble = pr<double, double>;
static_assert(is_trivially_copyable<pint>::value, "not trivially_copyable");
template <class A, class B>
struct tuple_size<pr<A, B>> : integral_constant<size_t, 2> {};
template <class A, class B>
struct tuple_element<0, pr<A, B>> {
using type = A;
};
template <class A, class B>
struct tuple_element<1, pr<A, B>> {
using type = B;
};
inline pdouble ToDouble(const pint& p) {
return pdouble{double(p.x), double(p.y)};
}
inline pint round(const pdouble& d) {
return pint{(int)round(d.x), (int)round(d.y)};
}
inline double norm(const pdouble& d) {
return sqrt((d.x * d.x) + (d.y * d.y));
}
inline double norm(const pint& d) {
return sqrt((d.x * d.x) + (d.y * d.y));
}
inline int norm2(const pint& d) {
return square(d.x) + square(d.y);
}
inline double norm2(const pdouble& d) {
return square(d.x) + square(d.y);
}
inline pdouble normalized(const pdouble& d) {
return d / norm(d);
}
inline double dot(const pdouble& a, const pdouble& b) {
return a.x * b.x + a.y * b.y;
}
inline double cross(const pdouble& a, const pdouble& b) {
return a.x * b.y - a.y * b.x;
}
template <class A, class B>
struct pr2 {
A a;
B b;
template <size_t I>
auto get() const {
if constexpr (I == 0) {
return a;
}
else if constexpr (I == 1) {
return b;
}
}
};
#include <cstdint>
struct Xor64 {
using result_type = uint32_t;
static constexpr result_type min() {
return 0;
}
static constexpr result_type max() {
return UINT32_MAX;
}
private:
Xor64(const Xor64& r) = delete;
Xor64& operator=(const Xor64& r) = delete;
public:
uint64_t x;
inline constexpr Xor64(uint64_t seed = 0) : x(88172645463325252ULL + seed) {
}
void SetDeviceRandom() {
random_device rd;
uint64_t s = (uint64_t(rd()) << 32) ^ uint64_t(rd());
if (s == 0) {
s = 0x123456789abcdef;
}
x = s;
}
inline constexpr uint64_t Get64() {
x ^= (x << 7);
return x ^= (x >> 9);
}
inline constexpr result_type operator()() {
return Get64() & 0xFFFFFFFF;
}
template <class T>
inline constexpr T operator()(T r) {
VASSERT(r <= 0xFFFFFFFF);
return ((Get64() & 0xFFFFFFFF) * r) >> 32;
}
inline double GetDouble() {
return Get64() / (double)UINT64_MAX;
}
inline bool GetProb(double E) {
return GetDouble() <= E;
}
inline double GetDoubleRange(double l, double r) {
return l + GetDouble() * (r - l);
}
};
template <class IT>
constexpr void Shuffle(IT&& begin, IT&& end, Xor64& rand) {
int size = int(end - begin);
if (size <= 1) {
return;
}
REP(i, size - 1) {
int j = i + rand(size - i);
swap(*(begin + i), *(begin + j));
}
}
template <class T, int CAP>
class CapArr {
private:
static_assert(is_trivially_copyable<T>::value);
using SizeType = typename conditional<CAP <= 256, u8, u32>::type;
T array_[CAP];
SizeType size_ = 0;
public:
CapArr() {
size_ = 0;
}
explicit CapArr(int size) {
resize(size);
}
CapArr(int size, const T& e) {
assign(size, e);
}
bool operator==(const CapArr<T, CAP>& r) const {
if (size_ != r.size_) {
return false;
}
REP(i, size_) {
if (!(array_[i] == r.array_[i])) {
return false;
}
}
return true;
}
template <class U, int U_CAP>
bool operator!=(const CapArr<U, U_CAP>& r) const {
return !(*this == r);
}
bool MemEqual(const CapArr<T, CAP>& r) const {
if (size_ != r.size_) {
return false;
}
return memcmp(data(), r.data(), sizeof(T) * size_) == 0;
}
constexpr int capacity() const {
return CAP;
}
int size() const {
return size_;
}
bool empty() const {
return size_ == 0;
}
bool exist() const {
return size_ != 0;
}
void clear() {
size_ = 0;
}
void resize(int size) {
size_ = size;
}
void assign(int size, const T& e) {
size_ = size;
if constexpr (sizeof(T) == 1) {
if constexpr (is_enum<T>::value) {
memset(data(), typename underlying_type<T>::type(e), size);
}
else {
memset(data(), *reinterpret_cast<const unsigned char*>(&e), size);
}
}
else {
for (int i = 0; i < size; ++i) {
array_[i] = e;
}
}
}
void AssignIota(int size) {
resize(size);
iota(begin(), end(), 0);
}
void Iota(int size) {
resize(size);
iota(begin(), end(), 0);
}
void MemAssign(int size, int byte) {
size_ = size;
memset(data(), byte, sizeof(T) * size);
}
void MemCopy(const CapArr<T, CAP>& from) {
size_ = from.size_;
memcpy(data(), from.data(), sizeof(T) * from.size_);
}
template <int CAP2>
void MemCopy(const CapArr<T, CAP2>& from) {
static_assert(CAP2 <= CAP);
size_ = from.size();
memcpy(data(), from.data(), sizeof(T) * size_);
}
const T* data() const {
return &array_[0];
}
T* data() {
return &array_[0];
}
T& front() {
return array_[0];
}
const T& front() const {
return array_[0];
}
T& back() {
return array_[size_ - 1];
}
const T& back() const {
return array_[size_ - 1];
}
T& operator[](int index) {
return array_[index];
}
const T& operator[](int index) const {
return array_[index];
}
T* begin() {
return &array_[0];
}
T* end() {
return &array_[size_];
}
const T* begin() const {
return &array_[0];
}
const T* end() const {
return &array_[size_];
}
[[nodiscard]] T& push() {
auto& ref = array_[size_];
++size_;
return ref;
}
void push(const T& e) {
array_[size_] = e;
++size_;
}
void pop() {
--size_;
}
int find(const T& value) const {
REP(i, size_) {
if (array_[i] == value) {
return i;
}
}
return -1;
}
bool contains(const T& value) const {
for (const auto& v : *this) {
if (v == value) {
return true;
}
}
return false;
}
void insert(int index, const T& value) {
insert(index, &value, 1);
}
void insert(int index, const T* mem, int size) {
if (index == size_) {
memcpy(data() + index, mem, sizeof(T) * size);
size_ += size;
}
else {
memmove(data() + index + size, data() + index, sizeof(T) * (size_ - index));
memcpy(data() + index, mem, sizeof(T) * size);
size_ += size;
}
}
template <int RCAP>
void append(const CapArr<T, RCAP>& r) {
insert(size(), r.data(), r.size());
}
void remove(int index) {
remove(index, index + 1);
}
void remove(int start, int end) {
int size = end - start;
memmove(data() + start, data() + end, sizeof(T) * (size_ - end));
size_ -= size;
}
void RemoveSwap(int index) {
array_[index] = array_[size_ - 1];
--size_;
}
void RemoveWithKeeps(const CapArr<int, CAP>& idxs) {
int to = 0;
for (int idx : idxs) {
array_[to] = array_[idx];
++to;
}
size_ = idxs.size();
}
void Remove(int start, int end) {
memmove(data() + start, data() + end, sizeof(T) * (size_ - end));
size_ -= end - start;
}
void RemoveInsert(int start, int end, const T* p, int size) {
int newEnd = start + size;
if (size_ - end > 0 && newEnd != end) {
memmove(data() + newEnd, data() + end, sizeof(T) * (size_ - end));
}
memcpy(data() + start, p, sizeof(T) * size);
size_ -= end - start;
size_ += size;
}
void sort() {
::sort(begin(), end());
}
void rsort() {
::sort(begin(), end(), greater<T>());
}
template <class LESS>
void sort(LESS&& less) {
::sort(begin(), end(), less);
}
void stable_sort() {
::stable_sort(begin(), end());
}
void stable_rsort() {
::stable_sort(begin(), end(), greater<T>());
}
template <class LESS>
void stable_sort(LESS&& less) {
::stable_sort(begin(), end(), less);
}
void idx_sort(CapArr<int, CAP>& idxs) {
idxs.Iota(size());
idxs.sort([&](int a, int b) { return array_[a] < array_[b]; });
}
void idx_rsort(CapArr<int, CAP>& idxs) {
idxs.Iota(size());
idxs.sort([&](int a, int b) { return array_[b] < array_[a]; });
}
void idx_stable_sort(CapArr<int, CAP>& idxs) {
idxs.Iota(size());
idxs.stable_sort([&](int a, int b) { return array_[a] < array_[b]; });
}
void idx_stable_rsort(CapArr<int, CAP>& idxs) {
idxs.Iota(size());
idxs.stable_sort([&](int a, int b) { return array_[b] < array_[a]; });
}
template <class LESS>
void nth_element(int n, LESS&& less) {
::nth_element(begin(), begin() + n, end(), less);
}
void reverse() {
::reverse(begin(), end());
}
template <class RAND>
void shuffle(RAND&& r) {
Shuffle(begin(), end(), r);
}
template <class RAND>
const T& choice(RAND&& r) const {
VASSERT(size_ > 0);
return array_[r(size_)];
}
};
template <class T, int CAPACITY>
struct CapacityQueue {
private:
array<T, CAPACITY> ar_ = {};
int start_ = 0;
int end_ = 0;
public:
inline void clear() {
start_ = 0;
end_ = 0;
}
inline void push(const T& v) {
ar_[end_] = v;
++end_;
}
[[nodiscard]]
inline T& push() {
T& ptr = ar_[end_];
++end_;
return ptr;
}
inline const T& get() const {
return ar_[start_];
}
inline T pop() {
return ar_[start_++];
}
inline bool empty() const {
return start_ == end_;
}
inline bool exist() const {
return start_ != end_;
}
inline int size() const {
return end_ - start_;
}
inline int total_push_count() const {
return end_;
}
const T& operator[](int i) const {
return ar_[i];
}
int end_size() const {
return end_;
}
int direct_start() const {
return start_;
}
int direct_end() const {
return end_;
}
inline auto begin() -> decltype(ar_.begin()) {
return ar_.begin() + start_;
}
inline auto end() -> decltype(ar_.begin()) {
return ar_.begin() + end_;
}
inline auto begin() const -> decltype(ar_.begin()) {
return ar_.begin() + start_;
}
inline auto end() const -> decltype(ar_.begin()) {
return ar_.begin() + end_;
}
const T& front() const {
return ar_[start_];
}
const T& back() const {
return ar_[end_ - 1];
}
};
template <class T, int CAPACITY>
using CapQue = CapacityQueue<T, CAPACITY>;
template <int CAP>
struct CapSet {
private:
using Key = typename conditional<CAP <= 256, u8, u32>::type;
CapArr<Key, CAP>
elemens;
array<Key, CAP> indexs;
public:
bool operator==(const CapSet<CAP>& r) const {
if (elemens.size() != r.elemens.size()) {
return false;
}
for (Key i : elemens) {
if (!r.contains(i)) {
return false;
}
}
return true;
}
constexpr int capacity() {
return CAP;
}
void fill(int n) {
elemens.resize(n);
iota(ALL(elemens), 0);
iota(indexs.begin(), indexs.begin() + n, 0);
}
template <class Key2, int CAP2>
void setfill(const CapArr<Key2, CAP2>& as) {
elemens.resize(as.size());
REP(ai, as.size()) {
indexs[as[ai]] = ai;
elemens[ai] = as[ai];
}
}
void clear() {
elemens.clear();
}
void set(Key i, bool exist) {
if (exist) {
fadd(i);
}
else {
fremove(i);
}
}
void add(Key i) {
indexs[i] = elemens.size();
elemens.push(i);
}
void fadd(Key i) {
if (contains(i)) {
return;
}
indexs[i] = elemens.size();
elemens.push(i);
}
void remove(Key i) {
Key removeIndex = indexs[i];
Key lastIndex = elemens.size() - 1;
if (removeIndex != lastIndex) {
elemens[removeIndex] = elemens[lastIndex];
indexs[elemens[lastIndex]] = removeIndex;
}
elemens.pop();
}
void fremove(Key i) {
if (!contains(i)) {
return;
}
Key removeIndex = indexs[i];
Key lastIndex = elemens.size() - 1;
if (removeIndex != lastIndex) {
elemens[removeIndex] = elemens[lastIndex];
indexs[elemens[lastIndex]] = removeIndex;
}
elemens.pop();
}
bool contains(Key i) const {
return indexs[i] < (Key)elemens.size() && elemens[indexs[i]] == i;
}
int size() const {
return elemens.size();
}
bool empty() const {
return elemens.empty();
}
Key operator[](int index) const {
return elemens[index];
}
auto begin() -> decltype(elemens.begin()) {
return elemens.begin();
}
auto end() -> decltype(elemens.begin()) {
return elemens.end();
}
auto begin() const -> decltype(elemens.begin()) {
return elemens.begin();
}
auto end() const -> decltype(elemens.begin()) {
return elemens.end();
}
void extend(const CapSet<CAP>& r) {
for (int s : r) {
add(s);
}
}
void fextend(const CapSet<CAP>& r) {
for (int s : r) {
fadd(s);
}
}
template <class RAND>
const Key& choice(RAND&& r) const {
return elemens.choice(r);
}
const CapArr<Key, CAP>& RefArray() const {
return elemens;
}
};
#include <bit>
template <class T, int CAP>
struct CapMap {
private:
using Key = typename conditional<CAP <= 256, u8, u32>::type;
CapArr<pr2<Key, T>, CAP>
elemens;
array<Key, CAP> indexs;
public:
bool operator==(const CapMap<T, CAP>& r) const {
if (elemens.size() != r.elemens.size()) {
return false;
}
for (auto&& [k, v] : elemens) {
if (!r.contains(k)) {
return false;
}
if (v != r.get(k)) {
return false;
}
}
return true;
}
bool operator!=(const CapMap<T, CAP>& r) const {
return !((*this) == r);
}
constexpr int capacity() {
return CAP;
}
void clear() {
elemens.clear();
}
void Clear() {
clear();
}
void set(Key i, const T& value) {
if (contains(i)) {
auto& e = elemens[indexs[i]];
e.b = value;
}
else {
indexs[i] = elemens.size();
auto& e = elemens.push();
e.a = i;
e.b = value;
}
}
const T& get(Key i) const {
return elemens[indexs[i]].b;
}
const T& get(Key i, const T& defaultValue) const {
if (contains(i)) {
return elemens[indexs[i]].b;
}
return defaultValue;
}
T& fref(Key i) {
if (contains(i)) {
return elemens[indexs[i]].b;
}
else {
indexs[i] = elemens.size();
auto& e = elemens.push();
e.a = i;
return e.b;
}
}
T& ref(Key i) {
return elemens[indexs[i]].b;
}
void AddValue(Key i, const T& addValue, const T& defaultValue) {
if (contains(i)) {
elemens[indexs[i]].b += addValue;
}
else {
indexs[i] = elemens.size();
auto& e = elemens.push();
e.a = i;
e.b = defaultValue + addValue;
}
}
void remove(Key i) {
Key removeIndex = indexs[i];
Key lastIndex = elemens.size() - 1;
if (removeIndex != lastIndex) {
elemens[removeIndex] = elemens[lastIndex];
indexs[elemens[lastIndex].a] = removeIndex;
}
elemens.pop();
}
bool contains(Key i) const {
return indexs[i] < (Key)elemens.size() && elemens[indexs[i]].a == i;
}
int size() const {
return elemens.size();
}
bool empty() const {
return elemens.empty();
}
Key AtIndex(int index) const {
return elemens[index].a;
}
auto begin() -> decltype(elemens.begin()) {
return elemens.begin();
}
auto end() -> decltype(elemens.begin()) {
return elemens.end();
}
auto begin() const -> decltype(elemens.begin()) {
return elemens.begin();
}
auto end() const -> decltype(elemens.begin()) {
return elemens.end();
}
};
template <class T, int CAPACITY>
struct CapacityRingDeque {
private:
array<T, CAPACITY> buf_;
int head_ = 0;
int tail_ = 0;
int count_ = 0;
public:
constexpr int capacity() const {
return CAPACITY;
}
inline void clear() {
head_ = 0;
tail_ = 0;
count_ = 0;
}
inline void push_back(const T& v) {
VASSERT(count_ < CAPACITY);
buf_[tail_] = v;
++tail_;
if (tail_ >= CAPACITY) {
tail_ = 0;
}
++count_;
}
inline void push_front(const T& v) {
VASSERT(count_ < CAPACITY);
--head_;
if (head_ < 0) {
head_ = CAPACITY - 1;
}
buf_[head_] = v;
++count_;
}
inline void pop_back() {
VASSERT(count_ > 0);
--tail_;
if (tail_ < 0) {
tail_ = CAPACITY - 1;
}
--count_;
}
inline void pop_front() {
VASSERT(count_ > 0);
++head_;
if (head_ >= CAPACITY) {
head_ = 0;
}
--count_;
}
inline int size() const {
return count_;
}
inline bool empty() const {
return count_ == 0;
}
inline const T& front() const {
return buf_[head_];
}
inline const T& back() const {
if (tail_ == 0) {
return buf_[CAPACITY - 1];
}
return buf_[tail_ - 1];
}
void GetArr(CapArr<T, CAPACITY>& a) const {
a.clear();
int j = head_;
REP(i, count_) {
a.push(buf_[j]);
++j;
if (j >= CAPACITY) {
j = 0;
}
}
}
};
#define NO_SWAP 0
template <class T, int CAP, class CMP>
struct CapIntervalHeap {
CMP cmp;
CapArr<T, CAP> buf_;
bool empty() const {
return buf_.empty();
}
int size() const {
return buf_.size();
}
constexpr int capacity() const {
return CAP;
}
void clear() {
buf_.clear();
}
const T& GetMin() const {
return buf_[0];
}
const T& GetMax() const {
return buf_.size() < 2 ? buf_[0] : buf_[1];
}
void push(const T& v) {
int c = buf_.size();
buf_.push(v);
if (c == 0) {
}
else if (c == 1) {
if (cmp(buf_[1], buf_[0])) {
swap(buf_[1], buf_[0]);
}
}
else if (c & 1) {
int cr = c;
int cl = cr - 1;
if (cmp(buf_[cr], buf_[cl])) {
swap(buf_[cr], buf_[cl]);
UpMin(cl);
}
else {
UpMax(cr);
}
}
else {
int pl = (((c >> 1) - 1) & ~1);
int pr = (pl | 1);
if (cmp(buf_[c], buf_[pl])) {
swap(buf_[c], buf_[pl]);
UpMin(pl);
}
else if (cmp(buf_[pr], buf_[c])) {
swap(buf_[pr], buf_[c]);
UpMax(pr);
}
else {
}
}
}
void PopMin() {
if (buf_.size() <= 1) {
buf_.pop();
}
else {
buf_[0] = buf_.back();
buf_.pop();
DownMin(0);
}
}
void PopMax() {
if (buf_.size() <= 2) {
buf_.pop();
}
else {
buf_[1] = buf_.back();
buf_.pop();
DownMax(1);
}
}
T ReplaceMin(const T& v) {
T ret = buf_[0];
buf_[0] = v;
if (buf_.size() >= 2) {
if (cmp(buf_[1], buf_[0])) {
swap(buf_[1], buf_[0]);
}
DownMin(0);
}
return ret;
}
private:
void UpMin(int c) {
T v = buf_[c];
while (c > 1) {
int p = (((c >> 1) - 1) & ~1);
if (cmp(v, buf_[p])) {
buf_[c] = buf_[p];
c = p;
}
else {
break;
}
}
buf_[c] = v;
}
void UpMax(int c) {
T v = buf_[c];
while (c > 1) {
int p = (((c >> 1) - 1) | 1);
if (cmp(buf_[p], v)) {
buf_[c] = buf_[p];
c = p;
}
else {
break;
}
}
buf_[c] = v;
}
void DownMin(int p) {
VASSERT((p & 1) == 0);
int size = buf_.size();
T v = buf_[p];
for (int l = ((p << 1) + 2); l < size; l = ((p << 1) + 2)) {
int r = l + 2;
int c = (r < size && cmp(buf_[r], buf_[l])) ? r : l;
if (cmp(buf_[c], v)) {
buf_[p] = buf_[c];
p = c;
}
else {
break;
}
int pr = p | 1;
if (pr >= size) {
break;
}
if (cmp(buf_[pr], v)) {
swap(buf_[pr], v);
}
}
buf_[p] = v;
}
void DownMax(int p) {
VASSERT((p & 1) == 1);
int size = buf_.size();
T v = buf_[p];
for (int l = ((p << 1) + 1); l < size; l = ((p << 1) + 1)) {
int r = l + 2;
int c = (r < size && cmp(buf_[l], buf_[r])) ? r : l;
if (cmp(v, buf_[c])) {
buf_[p] = buf_[c];
p = c;
}
else {
break;
}
int pl = p ^ 1;
if (cmp(v, buf_[pl])) {
swap(v, buf_[pl]);
}
}
buf_[p] = v;
}
};
template<class T, class COMPARERE = less<T>>
struct PriorityQueue : public priority_queue<T, vector<T>, COMPARERE> {
template <class D>
void Cut(int size, D&& deleter) {
if ((int)this->c.size() > size) {
int orgSize = (int)this->c.size();
for (int i = size; i < orgSize; ++i) {
deleter(this->c[i]);
}
this->c.resize(size);
}
}
vector<T>& Container() {
return this->c;
}
void Cut(int size) {
if ((int)this->c.size() > size) {
this->c.resize(size);
}
}
void Clear() {
this->c.clear();
}
};
struct CheckMapD {
private:
vector<u32> checked_;
u32 mark_ = 1;
public:
void Init(int size) {
checked_.resize(size, mark_);
Clear();
}
void SetSize(int size) {
checked_.resize(size, mark_);
}
void Clear() {
++mark_;
if (mark_ == 0) {
checked_.assign(checked_.size(), 0);
++mark_;
}
}
inline bool IsChecked(int i) const {
return checked_[i] == mark_;
}
bool Enter(int i) {
if (checked_[i] == mark_) {
return false;
}
checked_[i] = mark_;
return true;
}
inline bool operator[](int i) const {
return checked_[i] == mark_;
}
inline void Check(int i) {
checked_[i] = mark_;
}
inline void Reset(int i) {
checked_[i] = mark_ - 1;
}
};
template <class K>
struct CapHashSet {
uint32_t m_capacity;
K* m_keys;
CheckMapD m_states;
uint32_t m_mask;
uint32_t m_count = 0;
~CapHashSet() {
free(m_keys);
}
CapHashSet() {
}
CapHashSet(const CapHashSet&) = delete;
void operator=(const CapHashSet&) = delete;
CapHashSet(CapHashSet&& r) noexcept
: m_capacity(r.m_capacity),
m_keys(r.m_keys),
m_states(r.m_states),
m_mask(r.m_mask),
m_count(r.m_count)
{
r.m_capacity = 0;
r.m_keys = nullptr;
r.m_states.Clear();
r.m_mask = 0;
r.m_count = 0;
}
void init(uint32_t capacity) {
VASSERT(capacity > 0);
m_capacity = 1ULL << (32 - countl_zero(u32(capacity - 1)));
VASSERT(m_capacity >= capacity);
m_mask = m_capacity - 1;
m_keys = (K*)malloc(m_capacity * sizeof(K));
VASSERT(m_keys);
m_states.Init(m_capacity);
m_count = 0;
}
void clear() {
m_states.Clear();
m_count = 0;
}
inline void set(K key) {
uint32_t i = key & m_mask;
for (;;) {
if (m_states[(int)i]) {
if (key == m_keys[i]) {
break;
}
}
else {
m_states.Check((int)i);
m_keys[i] = key;
++m_count;
break;
}
(++i) &= m_mask;
}
}
inline void insert(K key) {
set(key);
}
inline bool contains(K key) const {
uint32_t i = key & m_mask;
for (;;) {
if (m_states[(int)i]) {
if (key == m_keys[i]) {
return true;
}
}
else {
break;
}
(++i) &= m_mask;
}
return false;
}
bool enter(K key) {
uint32_t i = key & m_mask;
for (;;) {
if (m_states[i]) {
if (key == m_keys[i]) {
return false;
}
}
else {
m_states.Check((int)i);
m_keys[i] = key;
++m_count;
return true;
}
(++i) &= m_mask;
}
}
int size() const {
return m_count;
}
};
template <int S>
struct CheckMapS {
private:
array<u32, S> checked_ = {};
u32 mark_ = 1;
public:
void Clear() {
++mark_;
if (mark_ == 0) {
checked_ = {};
++mark_;
}
}
bool IsChecked(int i) const {
return checked_[i] == mark_;
}
void Check(int i) {
checked_[i] = mark_;
}
void Reset(int i) {
checked_[i] = mark_ - 1;
}
bool Enter(int i) {
if (checked_[i] == mark_) {
return false;
}
checked_[i] = mark_;
return true;
}
bool operator[](int i) const {
return checked_[i] == mark_;
}
bool operator==(const CheckMapS<S>& r) const {
REP(i, S) {
if (this->IsChecked(i) != r.IsChecked(i)) {
return false;
}
}
return true;
}
};
template <class T, int S>
struct CheckMapDataS {
private:
array<T, S> data_;
array<u32, S> checked_ = {};
u32 mark_ = 1;
public:
void Clear() {
++mark_;
if (mark_ == 0) {
checked_ = {};
++mark_;
}
}
bool IsChecked(int i) const {
return checked_[i] == mark_;
}
void Check(int i) {
checked_[i] = mark_;
}
void Set(int i, const T& value) {
checked_[i] = mark_;
data_[i] = value;
}
void Reset(int i) {
checked_[i] = mark_ - 1;
}
const T& Get(int i) const {
VASSERT(checked_[i] == mark_);
return data_[i];
}
T& Ref(int i) {
VASSERT(checked_[i] == mark_);
return data_[i];
}
const T& Ref(int i) const {
VASSERT(checked_[i] == mark_);
return data_[i];
}
T& operator[](int i) {
VASSERT(checked_[i] == mark_);
return data_[i];
}
const T& operator[](int i) const {
VASSERT(checked_[i] == mark_);
return data_[i];
}
T GetIf(int i, const T& defaultValue) const {
if (checked_[i] == mark_) {
return data_[i];
}
return defaultValue;
}
};
template <class T>
T* mem_alloc(int size) {
#ifdef _MSC_VER
return (T*)_aligned_malloc(size * sizeof(T), alignof(T));
#else
return (T*)std::aligned_alloc(alignof(T), size * sizeof(T));
#endif
}
template <class T>
void mem_free(T* ptr) {
#ifdef _MSC_VER
_aligned_free(ptr);
#else
std::free(ptr);
#endif
}
namespace dvec_trivial {
template <class T>
struct dvec {
private:
static_assert(std::is_trivially_destructible_v<T>);
static_assert(std::is_trivially_copyable_v<T>);
static constexpr int DefaultMallocSize = 1;
public:
using dvec_tag = void;
private:
T* ptr_;
int size_;
int cap_;
public:
~dvec() {
if (ptr_) {
mem_free(ptr_);
}
}
dvec() : ptr_(nullptr), size_(0), cap_(0) {
}
explicit dvec(int size) : ptr_(mem_alloc<T>(size)), size_(size), cap_(size) {
for (int i = 0; i < size; ++i) {
new (&ptr_[i]) T();
}
}
explicit dvec(const std::vector<T>& vec)
: ptr_(mem_alloc<T>((int)vec.size())), size_((int)vec.size()), cap_((int)vec.size()) {
for (int i = 0; i < size_; ++i) {
new (&ptr_[i]) T(vec[i]);
}
}
dvec(int size, const T& v) : ptr_(mem_alloc<T>(size)), size_(size), cap_(size) {
for (int i = 0; i < size; ++i) {
new (&ptr_[i]) T(v);
}
}
dvec(const dvec& r) {
if (r.ptr_) {
ptr_ = mem_alloc<T>(r.size_);
size_ = r.size_;
cap_ = r.size_;
memcpy(ptr_, r.ptr_, sizeof(T) * size_);
}
else {
ptr_ = nullptr;
size_ = 0;
cap_ = 0;
}
}
dvec(dvec&& r) noexcept : ptr_(r.ptr_), size_(r.size_), cap_(r.cap_) {
r.ptr_ = nullptr;
r.size_ = 0;
r.cap_ = 0;
}
void operator=(const dvec& r) {
if (r.ptr_) {
if (r.size_ > cap_) {
mem_free(ptr_);
ptr_ = mem_alloc<T>(r.size_);
cap_ = r.size_;
}
size_ = r.size_;
memcpy(ptr_, r.ptr_, sizeof(T) * size_);
}
else {
size_ = 0;
}
}
void operator=(dvec&& r) noexcept {
std::swap(ptr_, r.ptr_);
std::swap(size_, r.size_);
std::swap(cap_, r.cap_);
}
bool operator==(const dvec& r) const {
if (size_ != r.size_) {
return false;
}
for (int i = 0; i < size_; ++i) {
if (ptr_[i] != r.ptr_[i]) {
return false;
}
}
return true;
}
bool operator!=(const dvec& r) const {
return !(*this == r);
}
bool empty() const {
return size_ == 0;
}
inline void clear() {
if constexpr (!std::is_trivially_destructible_v<T>) {
for (int i = 0; i < size_; ++i) {
ptr_[i].~T();
}
}
size_ = 0;
}
inline int size() const {
return size_;
}
inline int capacity() const {
return cap_;
}
inline T& operator[](int i) {
VASSERT(ptr_);
VASSERT(i >= 0 && i <= size_);
return ptr_[i];
}
inline const T& operator[](int i) const {
VASSERT(ptr_);
VASSERT(i >= 0 && i <= size_);
return ptr_[i];
}
inline T* data() {
return ptr_;
}
inline const T* data() const {
return ptr_;
}
T* begin() {
return ptr_;
}
const T* begin() const {
return ptr_;
}
T* end() {
return ptr_ + size_;
}
const T* end() const {
return ptr_ + size_;
}
T& front() {
VASSERT(size_ > 0);
return *ptr_;
}
const T& front() const {
VASSERT(size_ > 0);
return *ptr_;
}
T& back() {
VASSERT(size_ > 0);
return ptr_[size_ - 1];
}
const T& back() const {
VASSERT(size_ > 0);
return ptr_[size_ - 1];
}
void reserve(int size) {
VASSERT(size >= 0);
if (size > cap_) {
int newCap = max(DefaultMallocSize, max(size, cap_ * 2));
T* newPtr = mem_alloc<T>(newCap);
if (ptr_) {
memcpy(newPtr, ptr_, sizeof(T) * size_);
mem_free(ptr_);
}
ptr_ = newPtr;
cap_ = newCap;
}
}
void resizeR(int size) {
VASSERT(size >= 0);
reserve(size);
size_ = size;
}
void resize(int size) {
VASSERT(size >= 0);
reserve(size);
size_ = size;
}
void resize(int size, const T& v) {
VASSERT(size >= 0);
reserve(size);
for (int i = size_; i < size; ++i) {
ptr_[i] = v;
}
size_ = size;
}
void assign(int size, const T& v) {
VASSERT(size >= 0);
if (size > cap_) {
mem_free(ptr_);
ptr_ = mem_alloc<T>(size);
cap_ = size;
}
for (int i = 0; i < size; ++i) {
ptr_[i] = v;
}
size_ = size;
}
[[nodiscard]] T& pushR() {
if (size_ == cap_) {
reserve(size_ + 1);
}
return ptr_[size_++];
}
void push(const T& v) {
pushR() = v;
}
void pushEmpty() {
if (size_ == cap_) {
reserve(size_ + 1);
}
++size_;
}
void pop() {
VASSERT(size_ > 0);
--size_;
}
void remove(int idx) {
VASSERT(idx >= 0 && idx < size_);
if (idx + 1 < size_) {
memmove(ptr_ + idx, ptr_ + idx + 1, sizeof(T) * (size_ - 1 - idx));
}
--size_;
}
void removeSwap(int idx) {
VASSERT(idx >= 0 && idx < size_);
ptr_[idx] = ptr_[size_ - 1];
--size_;
}
void swapInsert(int idx, const T& v) {
VASSERT(idx >= 0 && idx <= size_);
if (size_ == cap_) {
reserve(size_ + 1);
}
ptr_[size_] = ptr_[idx];
ptr_[idx] = v;
++size_;
}
[[nodiscard]] T& insertR(int idx) {
VASSERT(idx >= 0 && idx <= size_);
if (size_ == cap_) {
int newCap = std::max(DefaultMallocSize, cap_ * 2);
T* newPtr = mem_alloc<T>(newCap);
if (ptr_) {
memcpy(newPtr, ptr_, sizeof(T) * idx);
if (idx < size_) {
memcpy(newPtr + idx + 1, ptr_ + idx, sizeof(T) * (size_ - idx));
}
mem_free(ptr_);
}
ptr_ = newPtr;
cap_ = newCap;
}
else {
if (idx < size_) {
memmove(ptr_ + idx + 1, ptr_ + idx, sizeof(T) * (size_ - idx));
}
}
++size_;
return ptr_[idx];
}
void resizeArea(int start, int end, int areaSize) {
VASSERT(start >= 0 && end >= 0);
VASSERT(start <= end);
VASSERT(areaSize >= 0);
int newSize = size_ - (end - start) + areaSize;
if (newSize > cap_) {
int newCap = std::max(DefaultMallocSize, cap_ * 2);
if (newSize > newCap) {
newCap = newSize * 3 / 2;
}
T* newPtr = mem_alloc<T>(newCap);
if (ptr_) {
memcpy(newPtr, ptr_, sizeof(T) * start);
if (end < size_) {
memcpy(newPtr + start + areaSize, ptr_ + end, sizeof(T) * (size_ - end));
}
mem_free(ptr_);
}
ptr_ = newPtr;
cap_ = newCap;
}
else {
if (end < size_) {
memmove(ptr_ + start + areaSize, ptr_ + end, sizeof(T) * (size_ - end));
}
}
size_ = newSize;
}
void RemoveInsert(int start, int end, const T* p, int size) {
int newEnd = start + size;
resizeArea(start, end, size);
memcpy(data() + start, p, sizeof(T) * size);
}
void extend(const dvec<T>& r) {
RemoveInsert(size_, size_, r.ptr_, r.size_);
}
int find(const T& v) const {
for (int i = 0; i < size_; ++i) {
if (ptr_[i] == v) {
return i;
}
}
return -1;
}
bool contains(const T& v) const {
for (int i = 0; i < size_; ++i) {
if (ptr_[i] == v) {
return true;
}
}
return false;
}
template <class RAND>
const T& choice(RAND&& r) const {
VASSERT(size_ > 0);
return ptr_[r(size_)];
}
};
};
namespace dvec_non_trivial {
template <class T>
struct dvec {
private:
static constexpr int DefaultMallocSize = 1;
public:
using dvec_tag = void;
private:
T* ptr_;
int size_;
int consted_;
int cap_;
public:
~dvec() {
if (ptr_) {
for (int i = 0; i < consted_; ++i) {
ptr_[i].~T();
}
mem_free(ptr_);
}
}
dvec() : ptr_(nullptr), size_(0), consted_(0), cap_(0) {
}
explicit dvec(int size) : ptr_(mem_alloc<T>(size)), size_(size), consted_(size), cap_(size) {
for (int i = 0; i < size; ++i) {
new (&ptr_[i]) T();
}
}
explicit dvec(const std::vector<T>& vec) {
int size = (int)vec.size();
ptr_ = mem_alloc<T>(size);
size_ = size;
consted_ = size;
cap_ = size;
;
for (int i = 0; i < size; ++i) {
new (&ptr_[i]) T(vec[i]);
}
}
dvec(int size, const T& v) : ptr_(mem_alloc<T>(size)), size_(size), consted_(size), cap_(size) {
for (int i = 0; i < size; ++i) {
new (&ptr_[i]) T(v);
}
}
dvec(const dvec& r) {
if (r.ptr_) {
ptr_ = mem_alloc<T>(r.size_);
size_ = r.size_;
consted_ = size_;
cap_ = r.size_;
for (int i = 0; i < size_; ++i) {
new (&ptr_[i]) T(r.ptr_[i]);
}
}
else {
ptr_ = nullptr;
size_ = 0;
consted_ = 0;
cap_ = 0;
}
}
dvec(dvec&& r) noexcept : ptr_(r.ptr_), size_(r.size_), consted_(r.consted_), cap_(r.cap_) {
r.ptr_ = nullptr;
r.size_ = 0;
r.consted_ = 0;
r.cap_ = 0;
}
void operator=(const dvec& r) {
if (r.size_ <= cap_) {
for (int i = 0; i < r.size_; ++i) {
if (i < consted_) {
ptr_[i] = r.ptr_[i];
}
else {
new (&ptr_[i]) T(r.ptr_[i]);
}
}
size_ = r.size_;
chmax(consted_, size_);
}
else {
for (int i = 0; i < consted_; ++i) {
ptr_[i].~T();
}
mem_free(ptr_);
ptr_ = mem_alloc<T>(r.cap_);
for (int i = 0; i < r.size_; ++i) {
new (&ptr_[i]) T(r.ptr_[i]);
}
size_ = r.size_;
consted_ = size_;
cap_ = r.cap_;
}
}
void operator=(dvec&& r) noexcept {
std::swap(ptr_, r.ptr_);
std::swap(size_, r.size_);
std::swap(consted_, r.consted_);
std::swap(cap_, r.cap_);
}
bool operator==(const dvec& r) const {
if (size_ != r.size_) {
return false;
}
for (int i = 0; i < size_; ++i) {
if (ptr_[i] != r.ptr_[i]) {
return false;
}
}
return true;
}
bool operator!=(const dvec& r) const {
return !(*this == r);
}
bool empty() const {
return size_ == 0;
}
inline void clear() {
size_ = 0;
}
inline int size() const {
return size_;
}
inline int constructed() const {
return consted_;
}
inline int capacity() const {
return cap_;
}
inline T& operator[](int i) {
VASSERT(ptr_);
VASSERT(i >= 0 && i <= size_);
return ptr_[i];
}
inline const T& operator[](int i) const {
VASSERT(ptr_);
VASSERT(i >= 0 && i <= size_);
return ptr_[i];
}
inline T* data() {
return ptr_;
}
inline const T* data() const {
return ptr_;
}
T* begin() {
return ptr_;
}
const T* begin() const {
return ptr_;
}
T* end() {
return ptr_ + size_;
}
const T* end() const {
return ptr_ + size_;
}
T& front() {
VASSERT(size_ > 0);
return *ptr_;
}
const T& front() const {
VASSERT(size_ > 0);
return *ptr_;
}
T& back() {
VASSERT(size_ > 0);
return ptr_[size_ - 1];
}
const T& back() const {
VASSERT(size_ > 0);
return ptr_[size_ - 1];
}
void reserve(int size) {
VASSERT(size >= 0);
if (size > cap_) {
int newCap = max(DefaultMallocSize, max(size, cap_ * 2));
T* newPtr = mem_alloc<T>(newCap);
if (ptr_) {
for (int i = 0; i < consted_; ++i) {
new (&newPtr[i]) T(std::move(ptr_[i]));
}
mem_free(ptr_);
}
ptr_ = newPtr;
cap_ = newCap;
}
}
void resizeR(int size) {
VASSERT(size >= 0);
if (size <= cap_) {
if (size > consted_) {
for (int i = consted_; i < size; ++i) {
new (&ptr_[i]) T();
}
consted_ = size;
}
size_ = size;
}
else {
int newCap = max(DefaultMallocSize, max(size, cap_ * 2));
T* newPtr = mem_alloc<T>(newCap);
if (ptr_) {
for (int i = 0; i < consted_; ++i) {
new (&newPtr[i]) T(std::move(ptr_[i]));
}
mem_free(ptr_);
}
ptr_ = newPtr;
cap_ = newCap;
VASSERT(size > consted_);
for (int i = consted_; i < size; ++i) {
new (&ptr_[i]) T();
}
consted_ = size;
size_ = size;
}
}
void resize(int size) {
resizeR(size);
}
void resize(int size, const T& v) {
int srcSize = size_;
resizeR(size);
for (int i = srcSize; i < size; ++i) {
ptr_[i] = v;
}
}
void assign(int size, const T& v) {
VASSERT(size >= 0);
if (size <= cap_) {
for (int i = 0; i < size; ++i) {
if (i < consted_) {
ptr_[i] = v;
}
else {
new (&ptr_[i]) T(v);
}
}
size_ = size;
chmax(consted_, size_);
}
else {
for (int i = 0; i < consted_; ++i) {
ptr_[i].~T();
}
int newCap = max(DefaultMallocSize, max(size, cap_ * 2));
mem_free(ptr_);
ptr_ = mem_alloc<T>(newCap);
for (int i = 0; i < size; ++i) {
new (&ptr_[i]) T(v);
}
size_ = size;
consted_ = size_;
cap_ = newCap;
}
}
[[nodiscard]] T& pushR() {
if (size_ < consted_) {
++size_;
return ptr_[size_ - 1];
}
else if (size_ == cap_) {
reserve(size_ + 1);
}
new (&ptr_[size_]) T();
++size_;
VASSERT(consted_ < size_);
consted_ = size_;
return ptr_[size_ - 1];
}
[[nodiscard]] T& push() {
return pushR();
}
void push(const T& v) {
pushR() = v;
}
void pushEmpty() {
if (size_ < consted_) {
++size_;
}
else if (size_ == cap_) {
reserve(size_ + 1);
}
new (&ptr_[size_]) T();
++size_;
VASSERT(consted_ < size_);
consted_ = size_;
}
void pop() {
--size_;
}
void remove(int idx) {
VASSERT(idx >= 0 && idx < size_);
if (idx + 1 < size_) {
T tmp = std::move(ptr_[idx]);
for (int i = idx + 1; i < size_; ++i) {
ptr_[i - 1] = std::move(ptr_[i]);
}
ptr_[size_ - 1] = std::move(tmp);
}
--size_;
}
void removeSwap(int idx) {
VASSERT(idx >= 0 && idx < size_);
if (idx + 1 < size_) {
swap(ptr_[idx], ptr_[size_ - 1]);
}
--size_;
}
[[nodiscard]] T& insertR(int idx) {
VASSERT(idx >= 0 && idx <= size_);
if (size_ == cap_) {
int newCap = std::max(DefaultMallocSize, cap_ * 2);
T* newPtr = mem_alloc<T>(newCap);
if (ptr_) {
for (int i = 0; i < idx; ++i) {
new (&newPtr[i]) T(std::move(ptr_[i]));
}
if (idx < consted_) {
for (int i = idx; i < consted_; ++i) {
new (&newPtr[i + 1]) T(std::move(ptr_[i]));
}
}
++consted_;
new (&newPtr[idx]) T();
mem_free(ptr_);
}
ptr_ = newPtr;
cap_ = newCap;
}
else {
if (idx < size_) {
if (size_ < consted_) {
T tmp = std::move(ptr_[size_]);
RFOR(i, idx, size_) {
ptr_[i + 1] = std::move(ptr_[i]);
}
ptr_[idx] = std::move(tmp);
}
else {
VASSERT(size_ == consted_);
RFOR(i, idx, size_) {
if (i + 1 == size_) {
new (&ptr_[i + 1]) T(std::move(ptr_[i]));
}
else {
ptr_[i + 1] = std::move(ptr_[i]);
}
}
new (&ptr_[idx]) T();
++consted_;
}
}
else {
if (size_ < consted_) {
}
else {
new (&ptr_[idx]) T();
++consted_;
}
}
}
++size_;
return ptr_[idx];
}
template <class RAND>
const T& choice(RAND&& r) const {
VASSERT(size_ > 0);
return ptr_[r(size_)];
}
};
};
template <class T>
using dvec = conditional_t<is_trivial_v<T>, dvec_trivial::dvec<T>, dvec_non_trivial::dvec<T>>;
template <class T, class CMP = std::less<T>>
struct dheap {
CMP cmp;
dvec<T> buf_;
void reserve(int size) {
buf_.reserve(size);
}
int capacity() const {
return buf_.capacity();
}
void clear() {
buf_.clear();
}
bool empty() const {
return buf_.empty();
}
bool exist() const {
return !buf_.empty();
}
int size() const {
return buf_.size();
}
const T& top() {
return buf_.front();
}
void push(const T& v) {
buf_.pushR() = v;
Up(buf_.size() - 1);
}
T pop() {
T ret = buf_.front();
if (buf_.size() >= 2) {
swap(buf_[0], buf_.back());
buf_.pop();
Down(0);
}
else {
buf_.pop();
}
return ret;
}
T popPush(const T& v) {
T ret = buf_.front();
buf_[0] = v;
if (buf_.size() >= 2) {
Down(0);
}
return ret;
}
T& BeginUpdateTop() {
return buf_.front();
}
void EndUpdateTop() {
if (buf_.size() >= 2) {
Down(0);
}
}
private:
void Up(int c) {
T v = buf_[c];
while (c > 0) {
int p = ((c - 1) >> 1);
if (cmp(buf_[p], v)) {
buf_[c] = buf_[p];
c = p;
}
else {
break;
}
}
buf_[c] = v;
}
void Down(int p) {
int size = buf_.size();
T v = buf_[p];
while (true) {
int l = (p << 1) + 1;
int r = l + 1;
int c;
if (r < size) {
c = cmp(buf_[r], buf_[l]) ? l : r;
}
else if (l < size) {
c = l;
}
else {
break;
}
if (cmp(v, buf_[c])) {
buf_[p] = buf_[c];
p = c;
}
else {
break;
}
}
buf_[p] = v;
}
};
template <class K, class V>
struct dhmap {
uint32_t m_capacity = 0;
K* m_keys = nullptr;
V* m_values = nullptr;
uint8_t* m_states = nullptr;
uint32_t m_mask = 0;
uint32_t m_count = 0;
~dhmap() {
free(m_keys);
free(m_values);
free(m_states);
}
dhmap() {
}
dhmap(const dhmap&) = delete;
void operator=(const dhmap&) = delete;
dhmap(dhmap&& r) noexcept
: m_capacity(r.m_capacity),
m_keys(r.m_keys),
m_values(r.m_values),
m_states(r.m_states),
m_mask(r.m_mask),
m_count(r.m_count)
{
r.m_capacity = 0;
r.m_keys = nullptr;
r.m_values = nullptr;
r.m_states = nullptr;
r.m_mask = 0;
r.m_count = 0;
}
void init(uint32_t capacity) {
if (capacity <= m_capacity) {
clear();
return;
}
free(m_keys);
free(m_values);
free(m_states);
m_capacity = 1ULL << bit_width(capacity);
m_mask = m_capacity - 1;
m_keys = (K*)malloc(m_capacity * sizeof(K));
m_values = (V*)malloc(m_capacity * sizeof(V));
m_states = (uint8_t*)calloc(m_capacity, sizeof(uint8_t));
m_count = 0;
}
void clear() {
memset(m_states, 0, m_capacity * sizeof(uint8_t));
m_count = 0;
}
void set(K key, const V& v) {
VASSERT(m_count <
m_capacity);
uint32_t i = key & m_mask;
REP(loop, m_capacity) {
if (m_states[i]) {
if (key == m_keys[i]) {
m_values[i] = v;
break;
}
}
else {
m_states[i] = 1;
m_keys[i] = key;
m_values[i] = v;
++m_count;
break;
}
(++i) &= m_mask;
}
}
V* try_get(K key) {
uint32_t i = key & m_mask;
REP(loop, m_capacity) {
if (m_states[i]) {
if (key == m_keys[i]) {
return &m_values[i];
}
}
else {
break;
}
(++i) &= m_mask;
}
return nullptr;
}
bool contains(K key) const {
uint32_t i = key & m_mask;
REP(loop, m_capacity) {
if (m_states[i]) {
if (key == m_keys[i]) {
return true;
}
}
else {
break;
}
(++i) &= m_mask;
}
return false;
}
int size() const {
return m_count;
}
int capacity() const {
return (int)m_capacity;
}
bool Direct(int i, K& k, V& v) const {
if (m_states[i]) {
k = m_keys[i];
v = m_values[i];
return true;
}
return false;
}
double GetUseRate() const {
return m_count / (double)m_capacity;
}
};
template <class K, class V>
struct dhmapR {
uint32_t m_capacity = 0;
K* m_keys = nullptr;
V* m_values = nullptr;
uint8_t* m_states = nullptr;
uint32_t m_mask = 0;
uint32_t m_count = 0;
dhmapR(const dhmapR&) = delete;
void operator=(const dhmapR&) = delete;
dhmapR() {
}
~dhmapR() {
free(m_keys);
free(m_values);
free(m_states);
}
void init(uint32_t capacity) {
if (capacity <= m_capacity) {
clear();
return;
}
free(m_keys);
free(m_values);
free(m_states);
m_capacity = 1ULL << bit_width(capacity);
m_mask = m_capacity - 1;
m_keys = (K*)malloc(m_capacity * sizeof(K));
m_values = (V*)malloc(m_capacity * sizeof(V));
m_states = (uint8_t*)calloc(m_capacity, sizeof(uint8_t));
m_count = 0;
}
void clear() {
memset(m_states, 0, m_capacity * sizeof(uint8_t));
m_count = 0;
}
inline void set(K key, const V& v) {
VASSERT(m_count <
m_capacity);
uint32_t i = key & m_mask;
REP(loop, m_capacity) {
if (m_states[i] == 1) {
if (key == m_keys[i]) {
m_values[i] = v;
break;
}
}
else {
m_states[i] = 1;
m_keys[i] = key;
m_values[i] = v;
++m_count;
break;
}
(++i) &= m_mask;
}
}
inline V* try_get(K key) {
uint32_t i = key & m_mask;
REP(loop, m_capacity) {
if (m_states[i] == 0) {
break;
}
else if (m_states[i] == 1) {
if (key == m_keys[i]) {
return &m_values[i];
}
}
(++i) &= m_mask;
}
return nullptr;
}
void remove(K key) {
uint32_t i = key & m_mask;
REP(loop, m_capacity) {
if (m_states[i] == 1) {
if (key == m_keys[i]) {
m_states[i] = 2;
--m_count;
return;
}
}
(++i) &= m_mask;
}
VABORT();
}
bool contains(K key) const {
uint32_t i = key & m_mask;
REP(loop, m_capacity) {
if (m_states[i] == 0) {
break;
}
else if (m_states[i] == 1) {
if (key == m_keys[i]) {
return true;
}
}
(++i) &= m_mask;
}
return false;
}
int size() const {
return m_count;
}
int capacity() const {
return (int)m_capacity;
}
inline double GetUseRate() const {
return m_count / (double)m_capacity;
}
};
#define DEF_CONTAINERS(name, size) \
template <class TYPE> \
using name##Box = array<TYPE, size>; \
template <class TYPE> \
using name##Arr = CapArr<TYPE, size>; \
template <class TYPE> \
using name##Que = CapQue<TYPE, size>; \
using name##Set = CapSet<size>; \
template <class TYPE> \
using name##Map = CapMap<TYPE, size>; \
template <class TYPE> \
using name##Deque = CapacityRingDeque<TYPE, size>; \
using name##Check = CheckMapS<size>;
constexpr int N = 100;
constexpr int K = 10;
constexpr int T = 10000;
DEF_CONTAINERS(N, N);
DEF_CONTAINERS(K, K);
#define PARAM_CATEGORY(NAME, VALUE, ...) int NAME = VALUE;
#define PARAM_INT(NAME, VALUE, LOWER_VALUE, UPPER_VALUE, ...) int NAME = VALUE;
#define PARAM_DOUBLE(NAME, VALUE, LOWER_VALUE, UPPER_VALUE, ...) double NAME = VALUE;
#define PARAM_LOWER(v)
#define PARAM_UPPER(v)
#define START_TUNING
#define END_TUNING
#define PARAM_GROUP(NAME)
#define PARAM_GROUP_END
#define IF_START(cond)
#define IF_END
template <class T>
struct InputParam {
T minValue_;
T maxValue_;
T value_;
InputParam(T minValue, T maxValue) {
minValue_ = minValue;
maxValue_ = maxValue;
}
void SetValue(T value) {
value_ = value;
}
double GetRate(double strong) const {
double r = (value_ - minValue_) / (double)(maxValue_ - minValue_) * 2.0 - 1.0;
return r * strong;
}
};
static double BlendDoubleParam(double baseValue, double minValue, double maxValue, initializer_list<double> rates) {
double totalRate = 1;
for (double rate : rates) {
totalRate += rate;
}
double value = baseValue * totalRate;
chmax(value, minValue);
chmin(value, maxValue);
return value;
}
static int BlendIntParam(double baseValue, int minValue, int maxValue, initializer_list<double> rates) {
double totalRate = 1;
for (double rate : rates) {
totalRate += rate;
}
int value = (int)round(baseValue * totalRate);
chmax(value, minValue);
chmin(value, maxValue);
return value;
}
#define PC PARAM_CATEGORY
#define PI PARAM_INT
#define PD PARAM_DOUBLE
constexpr
struct {
START_TUNING;
PI(InitialStateCount, 1, 1, 4, 1);
PC(TempType, 0, 0, 1, 2);
IF_START(TempType == 0);
PD(Type0_StartTemp, 0.1, 0.1, 100.0, 0.0);
PD(Type0_EndTemp, 0.01, 0.1, 10.0, 0.0);
IF_END;
IF_START(TempType == 1);
PD(Type1_StartTemp, 1, 0.1, 100.0, 0.0);
PD(Type1_EndTemp, 0.1, 0.1, 10.0, 0.0);
IF_END;
IF_START(TempType == 2);
PD(Type2_StartTemp, 300, 0.1, 100.0, 0.0);
PD(Type2_EndTemp, 5, 0.1, 10.0, 0.0);
PD(Type2_TempPow, 2.0, 1.0, 3.0, 1.0);
IF_END;
END_TUNING;
PD(RollbackStartRate, 0, 0.0, 0.15, 0.0, 1.0);
PI(RollbackCount, 10000, 100, 100000, 1);
PD(RollbackNextMulti, 1.0, 0.9, 1.1, 0.1);
PI(MinRollbackCount, 100, 100, 300, 1);
PI(UpdateTmpMaskBit, 8, 0, 10, 0, 16);
} HP;
#undef PC
#undef PI
#undef PD
template <class T>
bool SetMax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T>
bool SetMin(T& a, const T& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
struct IOResult {
dvec<s8> commands_;
void Init() {
commands_.clear();
}
void PushMove(s8 to) {
commands_.push((s8)to);
}
void PushChange() {
commands_.push(-1);
}
void Output(ostream& os) const {
REP(i, commands_.size()) {
os << (int)commands_[i] << endl;
}
}
};
struct IOServer {
NBox<dvec<int>> arounds_;
NBox<pint> points_;
void InitInput(ChronoTimer& timer) {
istream& is = cin;
int dummy;
is >> dummy;
timer.Init();
int M;
is >> M;
is >> dummy >> dummy;
REP(i, M) {
int u, v;
is >> u >> v;
arounds_[u].push(v);
arounds_[v].push(u);
}
REP(i, N) {
int x, y;
is >> x >> y;
points_[i] = pint{x, y};
}
}
void Input() {
istream& is = cin;
}
void Output(IOResult& result) {
ostream& os = cout;
result.Output(os);
}
void Finalize() {
}
};
IOServer server;
Xor64 rand_;
#include <cstdint>
#include <cassert>
template <int MAX_BITS>
struct BitVec {
static_assert(MAX_BITS > 0, "MAX_BITS must be positive");
static constexpr int WORDS = (MAX_BITS + 63) / 64;
uint64_t w[WORDS];
uint16_t len;
BitVec() {
clear();
}
inline int size() const {
return len;
}
inline void clear() {
for (int i = 0; i < WORDS; ++i) w[i] = 0;
len = 0;
}
inline void push_back(bool bit) {
assert(len < MAX_BITS);
if (bit) {
w[len >> 6] |= (1ull << (len & 63));
}
++len;
}
inline bool operator==(const BitVec& o) const {
if (len != o.len) return false;
for (int i = 0; i < WORDS; ++i) {
if (w[i] != o.w[i]) return false;
}
return true;
}
inline uint64_t hash() const {
auto mix = [](uint64_t x) {
x += 0x9e3779b97f4a7c15ull;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ull;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebull;
return x ^ (x >> 31);
};
uint64_t h = mix((uint64_t)len);
for (int i = 0; i < WORDS; ++i) {
h ^= mix(w[i] + (uint64_t)(i + 1));
}
return h;
}
};
struct BitVec64 {
uint64_t bits;
uint8_t len;
BitVec64() : bits(0), len(0) {
}
inline void clear() {
bits = 0;
len = 0;
}
inline void push_back(bool bit) {
assert(len < 64);
if (bit) bits |= (1ull << len);
++len;
}
inline bool operator==(const BitVec64& o) const {
return len == o.len && bits == o.bits;
}
inline uint64_t hash() const {
uint64_t h = bits ^ (uint64_t(len) << 58);
h ^= h >> 33;
h *= 0xff51afd7ed558ccdULL;
h ^= h >> 33;
return h;
}
};
#include <vector>
class HashPersistentSetPool {
public:
struct Node {
uint64_t h;
Node* next;
};
void reserve(size_t reserve_nodes) {
pool_.reserve(reserve_nodes);
}
inline Node* alloc(uint64_t h, Node* next) {
pool_.push_back({h, next});
return &pool_.back();
}
class Set {
public:
Set() : head_(nullptr), pool_(nullptr) {
}
Set(Node* h, HashPersistentSetPool* p) : head_(h), pool_(p) {
}
inline bool contains(uint64_t h) const {
for (Node* p = head_; p; p = p->next) {
if (p->h == h) return true;
}
return false;
}
inline Set insert(uint64_t h) const {
return Set(pool_->alloc(h, head_), pool_);
}
inline bool empty() const {
return head_ == nullptr;
}
private:
Node* head_;
HashPersistentSetPool* pool_;
};
inline Set empty_set() {
return Set(nullptr, this);
}
size_t allocated() const {
return pool_.size();
}
private:
std::vector<Node> pool_;
};
class HashPersistentSet64 {
public:
struct Node {
uint64_t h;
Node* next;
};
void reserve(size_t reserve_nodes) {
pool_.reserve(reserve_nodes);
}
class Set {
public:
Set() : head_(nullptr), owner_(nullptr) {
}
Set(Node* h, HashPersistentSet64* o) : head_(h), owner_(o) {
}
inline bool contains(uint64_t h) const {
for (Node* p = head_; p; p = p->next) {
if (p->h == h) return true;
}
return false;
}
inline Set insert(uint64_t h) const {
assert(owner_);
return Set(owner_->alloc(h, head_), owner_);
}
inline bool empty() const {
return head_ == nullptr;
}
private:
Node* head_;
HashPersistentSet64* owner_;
};
inline Set empty_set() {
return Set(nullptr, this);
}
size_t allocated() const {
return pool_.size();
}
private:
std::vector<Node> pool_;
inline Node* alloc(uint64_t h, Node* next) {
pool_.push_back({h, next});
return &pool_.back();
}
};
struct PathMat {
array<NBox<NBox<NArr<s8>>>, N + 1> pathMat_;
void Init() {
for (auto& v : pathMat_) {
for (auto& w : v) {
for (auto& x : w) {
x.clear();
}
}
}
NQue<int> que;
NArr<int> dists;
NArr<int> froms;
REP(prev, N + 1) {
REP(start, N) {
if (start == prev) {
continue;
}
que.clear();
dists.assign(N, INT_MAX);
froms.assign(N, -1);
{
que.push(start);
dists[start] = 0;
froms[start] = -1;
}
while (!que.empty()) {
int p = que.pop();
for (int n : server.arounds_[p]) {
if (prev != N) {
if (p == start && n == prev) {
continue;
}
}
int d = dists[p] + 1;
if (d < dists[n]) {
if (n >= K) {
que.push(n);
}
dists[n] = d;
froms[n] = p;
}
}
}
REP(end, N) {
auto& path = pathMat_[prev][start][end];
path.clear();
int p = end;
while (p != -1) {
path.push(p);
p = froms[p];
}
if (path.size() < 2) {
path.clear();
}
else {
reverse(ALL(path));
}
}
}
}
}
};
using DynBitset = BitVec64;
HashPersistentSet64 pool_;
void Ready() {
pool_.reserve(1 << 20);
}
struct State {
int prev_ = -1;
int cur_ = -1;
DynBitset cone_;
KBox<HashPersistentSet64::Set> shopsIces_;
NBox<bool> changed_ = {};
int changeCount_ = 0;
int score_ = 0;
IOResult result_;
void Init() {
cur_ = 0;
result_.Init();
REP(i, K) {
shopsIces_[i] = pool_.empty_set();
}
}
void SetInvalid() {
cur_ = -1;
}
bool IsInvalid() const {
return cur_ < 0;
}
int GetTurn() const {
return (int)result_.commands_.size();
}
void CalcMoved(int n, DynBitset& cone, int& score) const {
cone = cone_;
score = score_;
if (n < K) {
if (shopsIces_[n].contains(cone_.hash())) {
}
else {
++score;
}
cone.clear();
}
else {
cone.push_back(changed_[n]);
}
}
void Move(int n) {
result_.PushMove(n);
if (n < K) {
if (shopsIces_[n].contains(cone_.hash())) {
}
else {
shopsIces_[n] = shopsIces_[n].insert(cone_.hash());
++score_;
}
cone_.clear();
}
else {
cone_.push_back(changed_[n]);
}
prev_ = cur_;
cur_ = n;
}
void ChangeColor() {
VASSERT(cur_ >= K);
VASSERT(changed_[cur_] == false);
result_.PushChange();
changed_[cur_] = !changed_[cur_];
}
};
struct Solver {
void Run() {
Ready();
IOResult bestResult;
int bestScore = -1;
IOResult result;
int score;
int tryCount = 0;
while (true) {
if (!SolverDP(result, score)) {
break;
}
++tryCount;
if (score > bestScore) {
bestScore = score;
bestResult = result;
}
}
cerr << "tryCount: " << tryCount << endl;
server.Output(bestResult);
}
bool SolverDP(IOResult& result, int& bestScore) {
array<NBox<State>, 2> dps;
dps[0][0].Init();
int dpi = 0;
bestScore = -1;
REP(t, T - 1) {
if (t % 100 == 0) {
if (timer_.IsOver()) {
return false;
}
}
REP(i, N) {
dps[1 - dpi][i].SetInvalid();
}
constexpr double startProb = 0.001;
constexpr double endProb = 0.012;
double timeRate = t / double(T);
double prob = startProb * pow(endProb / startProb, timeRate);
REP(cur, N) {
auto& curState = dps[dpi][cur];
if (curState.cur_ != cur) {
continue;
}
if (curState.GetTurn() >= T) {
if (curState.score_ > bestScore) {
bestScore = curState.score_;
result = curState.result_;
}
continue;
}
if (cur >= K) {
if (curState.GetTurn() < T - 1 && curState.changed_[cur] == false) {
double p = prob;
int one = 0;
int zero = 0;
int shop = 0;
for (int n : server.arounds_[curState.cur_]) {
if (n < K) {
++shop;
}
else {
if (curState.changed_[n]) {
++one;
}
else {
++zero;
}
}
}
if (one == 0 || timeRate > 0.5) {
p *= 1.5;
}
else {
p *= 0.5;
}
if (rand_.GetProb(p)) {
curState.ChangeColor();
}
}
}
VASSERT(curState.GetTurn() < T);
for (int n : server.arounds_[curState.cur_]) {
if (n == curState.prev_) {
continue;
}
auto& nextState = dps[1 - dpi][n];
if (nextState.IsInvalid()) {
nextState = curState;
nextState.Move(n);
}
else {
DynBitset movecCone;
int movedScore;
curState.CalcMoved(n, movecCone, movedScore);
auto Eval = [&](int score, const DynBitset& cone, int changeCount) -> double {
return score + cone.len * 0.00001 - changeCount * 0.01;
};
double nextEval = Eval(nextState.score_, nextState.cone_, nextState.changeCount_);
double movedEval = Eval(movedScore, movecCone, curState.changeCount_);
if (movedEval > nextEval) {
nextState = curState;
nextState.Move(n);
}
}
}
}
dpi = 1 - dpi;
}
cauto& dp = dps[dpi];
int bestIdx = -1;
REP(i, N) {
cauto& state = dp[i];
if (!state.IsInvalid()) {
if (state.score_ > bestScore) {
bestScore = state.score_;
bestIdx = i;
}
}
}
if (bestIdx >= 0) {
result = dp[bestIdx].result_;
}
return true;
}
};
struct Main {
void Run(int argc, const char* argv[]) {
VASSERT(argc == 1);
server.InitInput(timer_);
timer_.StartMs(TIME_LIMIT);
static Solver solver;
solver.Run();
server.Finalize();
}
};
Submission Info
| Submission Time |
|
| Task |
A - Ice Cream Collection |
| User |
bowwowforeach |
| Language |
C++23 (Clang 21.1.0) |
| Score |
166629 |
| Code Size |
85266 Byte |
| Status |
AC |
| Exec Time |
1963 ms |
| Memory |
13304 KiB |
Judge Result
| Set Name |
test_ALL |
| Score / Max Score |
166629 / 1500000 |
| Status |
|
| Set Name |
Test Cases |
| test_ALL |
test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt, test_0050.txt, test_0051.txt, test_0052.txt, test_0053.txt, test_0054.txt, test_0055.txt, test_0056.txt, test_0057.txt, test_0058.txt, test_0059.txt, test_0060.txt, test_0061.txt, test_0062.txt, test_0063.txt, test_0064.txt, test_0065.txt, test_0066.txt, test_0067.txt, test_0068.txt, test_0069.txt, test_0070.txt, test_0071.txt, test_0072.txt, test_0073.txt, test_0074.txt, test_0075.txt, test_0076.txt, test_0077.txt, test_0078.txt, test_0079.txt, test_0080.txt, test_0081.txt, test_0082.txt, test_0083.txt, test_0084.txt, test_0085.txt, test_0086.txt, test_0087.txt, test_0088.txt, test_0089.txt, test_0090.txt, test_0091.txt, test_0092.txt, test_0093.txt, test_0094.txt, test_0095.txt, test_0096.txt, test_0097.txt, test_0098.txt, test_0099.txt, test_0100.txt, test_0101.txt, test_0102.txt, test_0103.txt, test_0104.txt, test_0105.txt, test_0106.txt, test_0107.txt, test_0108.txt, test_0109.txt, test_0110.txt, test_0111.txt, test_0112.txt, test_0113.txt, test_0114.txt, test_0115.txt, test_0116.txt, test_0117.txt, test_0118.txt, test_0119.txt, test_0120.txt, test_0121.txt, test_0122.txt, test_0123.txt, test_0124.txt, test_0125.txt, test_0126.txt, test_0127.txt, test_0128.txt, test_0129.txt, test_0130.txt, test_0131.txt, test_0132.txt, test_0133.txt, test_0134.txt, test_0135.txt, test_0136.txt, test_0137.txt, test_0138.txt, test_0139.txt, test_0140.txt, test_0141.txt, test_0142.txt, test_0143.txt, test_0144.txt, test_0145.txt, test_0146.txt, test_0147.txt, test_0148.txt, test_0149.txt |
| Case Name |
Status |
Exec Time |
Memory |
| test_0000.txt |
AC |
1963 ms |
11028 KiB |
| test_0001.txt |
AC |
1957 ms |
11908 KiB |
| test_0002.txt |
AC |
1959 ms |
11552 KiB |
| test_0003.txt |
AC |
1956 ms |
11316 KiB |
| test_0004.txt |
AC |
1961 ms |
10736 KiB |
| test_0005.txt |
AC |
1956 ms |
10104 KiB |
| test_0006.txt |
AC |
1959 ms |
11036 KiB |
| test_0007.txt |
AC |
1959 ms |
10520 KiB |
| test_0008.txt |
AC |
1958 ms |
11428 KiB |
| test_0009.txt |
AC |
1957 ms |
10544 KiB |
| test_0010.txt |
AC |
1958 ms |
11104 KiB |
| test_0011.txt |
AC |
1957 ms |
10296 KiB |
| test_0012.txt |
AC |
1959 ms |
9736 KiB |
| test_0013.txt |
AC |
1958 ms |
11036 KiB |
| test_0014.txt |
AC |
1956 ms |
11148 KiB |
| test_0015.txt |
AC |
1957 ms |
10392 KiB |
| test_0016.txt |
AC |
1959 ms |
11000 KiB |
| test_0017.txt |
AC |
1959 ms |
11348 KiB |
| test_0018.txt |
AC |
1956 ms |
10652 KiB |
| test_0019.txt |
AC |
1959 ms |
10212 KiB |
| test_0020.txt |
AC |
1960 ms |
11912 KiB |
| test_0021.txt |
AC |
1956 ms |
12308 KiB |
| test_0022.txt |
AC |
1961 ms |
10500 KiB |
| test_0023.txt |
AC |
1960 ms |
10672 KiB |
| test_0024.txt |
AC |
1958 ms |
11352 KiB |
| test_0025.txt |
AC |
1956 ms |
10760 KiB |
| test_0026.txt |
AC |
1956 ms |
11112 KiB |
| test_0027.txt |
AC |
1958 ms |
11628 KiB |
| test_0028.txt |
AC |
1959 ms |
10600 KiB |
| test_0029.txt |
AC |
1959 ms |
10824 KiB |
| test_0030.txt |
AC |
1957 ms |
11180 KiB |
| test_0031.txt |
AC |
1959 ms |
10460 KiB |
| test_0032.txt |
AC |
1959 ms |
10164 KiB |
| test_0033.txt |
AC |
1958 ms |
11364 KiB |
| test_0034.txt |
AC |
1958 ms |
11988 KiB |
| test_0035.txt |
AC |
1957 ms |
8852 KiB |
| test_0036.txt |
AC |
1957 ms |
9212 KiB |
| test_0037.txt |
AC |
1958 ms |
12136 KiB |
| test_0038.txt |
AC |
1959 ms |
10336 KiB |
| test_0039.txt |
AC |
1959 ms |
11908 KiB |
| test_0040.txt |
AC |
1957 ms |
11344 KiB |
| test_0041.txt |
AC |
1957 ms |
10048 KiB |
| test_0042.txt |
AC |
1957 ms |
11676 KiB |
| test_0043.txt |
AC |
1958 ms |
9568 KiB |
| test_0044.txt |
AC |
1959 ms |
11124 KiB |
| test_0045.txt |
AC |
1957 ms |
10804 KiB |
| test_0046.txt |
AC |
1959 ms |
11308 KiB |
| test_0047.txt |
AC |
1957 ms |
10068 KiB |
| test_0048.txt |
AC |
1960 ms |
10540 KiB |
| test_0049.txt |
AC |
1960 ms |
10344 KiB |
| test_0050.txt |
AC |
1957 ms |
9604 KiB |
| test_0051.txt |
AC |
1957 ms |
10916 KiB |
| test_0052.txt |
AC |
1959 ms |
9452 KiB |
| test_0053.txt |
AC |
1956 ms |
11120 KiB |
| test_0054.txt |
AC |
1956 ms |
10908 KiB |
| test_0055.txt |
AC |
1956 ms |
9320 KiB |
| test_0056.txt |
AC |
1957 ms |
11344 KiB |
| test_0057.txt |
AC |
1959 ms |
9616 KiB |
| test_0058.txt |
AC |
1957 ms |
11976 KiB |
| test_0059.txt |
AC |
1960 ms |
10984 KiB |
| test_0060.txt |
AC |
1961 ms |
9492 KiB |
| test_0061.txt |
AC |
1957 ms |
12340 KiB |
| test_0062.txt |
AC |
1956 ms |
10600 KiB |
| test_0063.txt |
AC |
1957 ms |
11184 KiB |
| test_0064.txt |
AC |
1956 ms |
12116 KiB |
| test_0065.txt |
AC |
1959 ms |
11824 KiB |
| test_0066.txt |
AC |
1961 ms |
11092 KiB |
| test_0067.txt |
AC |
1958 ms |
9824 KiB |
| test_0068.txt |
AC |
1958 ms |
10560 KiB |
| test_0069.txt |
AC |
1957 ms |
10056 KiB |
| test_0070.txt |
AC |
1957 ms |
11568 KiB |
| test_0071.txt |
AC |
1957 ms |
11136 KiB |
| test_0072.txt |
AC |
1959 ms |
10968 KiB |
| test_0073.txt |
AC |
1958 ms |
11220 KiB |
| test_0074.txt |
AC |
1959 ms |
10248 KiB |
| test_0075.txt |
AC |
1957 ms |
11564 KiB |
| test_0076.txt |
AC |
1957 ms |
9412 KiB |
| test_0077.txt |
AC |
1960 ms |
11388 KiB |
| test_0078.txt |
AC |
1957 ms |
10332 KiB |
| test_0079.txt |
AC |
1959 ms |
10468 KiB |
| test_0080.txt |
AC |
1957 ms |
10232 KiB |
| test_0081.txt |
AC |
1958 ms |
10360 KiB |
| test_0082.txt |
AC |
1957 ms |
12176 KiB |
| test_0083.txt |
AC |
1956 ms |
10516 KiB |
| test_0084.txt |
AC |
1956 ms |
11316 KiB |
| test_0085.txt |
AC |
1957 ms |
11180 KiB |
| test_0086.txt |
AC |
1956 ms |
9592 KiB |
| test_0087.txt |
AC |
1956 ms |
11624 KiB |
| test_0088.txt |
AC |
1960 ms |
10580 KiB |
| test_0089.txt |
AC |
1956 ms |
9852 KiB |
| test_0090.txt |
AC |
1956 ms |
11696 KiB |
| test_0091.txt |
AC |
1959 ms |
12048 KiB |
| test_0092.txt |
AC |
1960 ms |
10864 KiB |
| test_0093.txt |
AC |
1957 ms |
11256 KiB |
| test_0094.txt |
AC |
1960 ms |
10340 KiB |
| test_0095.txt |
AC |
1957 ms |
10424 KiB |
| test_0096.txt |
AC |
1957 ms |
10640 KiB |
| test_0097.txt |
AC |
1957 ms |
10712 KiB |
| test_0098.txt |
AC |
1956 ms |
11356 KiB |
| test_0099.txt |
AC |
1956 ms |
11840 KiB |
| test_0100.txt |
AC |
1958 ms |
12152 KiB |
| test_0101.txt |
AC |
1956 ms |
11068 KiB |
| test_0102.txt |
AC |
1960 ms |
9868 KiB |
| test_0103.txt |
AC |
1958 ms |
10192 KiB |
| test_0104.txt |
AC |
1959 ms |
9908 KiB |
| test_0105.txt |
AC |
1957 ms |
10960 KiB |
| test_0106.txt |
AC |
1957 ms |
11544 KiB |
| test_0107.txt |
AC |
1958 ms |
10588 KiB |
| test_0108.txt |
AC |
1956 ms |
9944 KiB |
| test_0109.txt |
AC |
1957 ms |
9992 KiB |
| test_0110.txt |
AC |
1958 ms |
10724 KiB |
| test_0111.txt |
AC |
1957 ms |
12524 KiB |
| test_0112.txt |
AC |
1956 ms |
10320 KiB |
| test_0113.txt |
AC |
1960 ms |
10580 KiB |
| test_0114.txt |
AC |
1958 ms |
11100 KiB |
| test_0115.txt |
AC |
1959 ms |
10932 KiB |
| test_0116.txt |
AC |
1958 ms |
11352 KiB |
| test_0117.txt |
AC |
1956 ms |
10824 KiB |
| test_0118.txt |
AC |
1956 ms |
11220 KiB |
| test_0119.txt |
AC |
1956 ms |
10672 KiB |
| test_0120.txt |
AC |
1956 ms |
11196 KiB |
| test_0121.txt |
AC |
1957 ms |
12096 KiB |
| test_0122.txt |
AC |
1956 ms |
11268 KiB |
| test_0123.txt |
AC |
1957 ms |
9440 KiB |
| test_0124.txt |
AC |
1961 ms |
11096 KiB |
| test_0125.txt |
AC |
1956 ms |
10640 KiB |
| test_0126.txt |
AC |
1958 ms |
10072 KiB |
| test_0127.txt |
AC |
1956 ms |
9936 KiB |
| test_0128.txt |
AC |
1957 ms |
10620 KiB |
| test_0129.txt |
AC |
1957 ms |
10152 KiB |
| test_0130.txt |
AC |
1956 ms |
10068 KiB |
| test_0131.txt |
AC |
1957 ms |
11172 KiB |
| test_0132.txt |
AC |
1958 ms |
11456 KiB |
| test_0133.txt |
AC |
1956 ms |
11588 KiB |
| test_0134.txt |
AC |
1960 ms |
10868 KiB |
| test_0135.txt |
AC |
1957 ms |
10744 KiB |
| test_0136.txt |
AC |
1957 ms |
11524 KiB |
| test_0137.txt |
AC |
1957 ms |
10972 KiB |
| test_0138.txt |
AC |
1956 ms |
10376 KiB |
| test_0139.txt |
AC |
1956 ms |
11180 KiB |
| test_0140.txt |
AC |
1960 ms |
13304 KiB |
| test_0141.txt |
AC |
1957 ms |
10092 KiB |
| test_0142.txt |
AC |
1958 ms |
12164 KiB |
| test_0143.txt |
AC |
1958 ms |
9996 KiB |
| test_0144.txt |
AC |
1957 ms |
11080 KiB |
| test_0145.txt |
AC |
1960 ms |
10512 KiB |
| test_0146.txt |
AC |
1956 ms |
9256 KiB |
| test_0147.txt |
AC |
1960 ms |
10188 KiB |
| test_0148.txt |
AC |
1957 ms |
10636 KiB |
| test_0149.txt |
AC |
1957 ms |
10640 KiB |