proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: Commonly used utilities for competitive programming (tools/util.hpp)

They are miscellaneous code snippets for competitive programming.

Warning

This file contains code snippets convenient to competitive programming but not allowed in C++ standard. Therefore, it makes the program ill-formed to include this file, and may cause undefined behavior.

Constraints

Time Complexity

License

Author

Depends on

Verified with

Code

#ifndef TOOLS_UTIL_HPP
#define TOOLS_UTIL_HPP

// To see the details of my library, visit my GitHub Pages.
// https://anqooqie.github.io/proconlib/

#ifdef LOCAL
  #ifndef _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG
  #endif
#else
  #ifndef NDEBUG
    #define NDEBUG
  #endif
#endif

#include <bits/stdc++.h>
#include "tools/resize.hpp"
#include "tools/fill.hpp"
#include "tools/extend_input.hpp"
#include "tools/extend_output.hpp"
#include "tools/extend_hash.hpp"

using ll = long long;
using ull = unsigned long long;
using i32 = ::std::int32_t;
using u32 = ::std::uint32_t;
using i64 = ::std::int64_t;
using u64 = ::std::uint64_t;

#define ALL(x) ::std::begin(x), ::std::end(x)
#define REP(i, n) for (long long i = 0, i##_len = static_cast<long long>(n); i < i##_len; ++i)

#endif

#line 1 "tools/util.hpp"



// To see the details of my library, visit my GitHub Pages.
// https://anqooqie.github.io/proconlib/

#ifdef LOCAL
  #ifndef _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG
  #endif
#else
  #ifndef NDEBUG
    #define NDEBUG
  #endif
#endif

#include <bits/stdc++.h>
#line 1 "tools/resize.hpp"



#line 8 "tools/resize.hpp"

namespace tools {
  template <class T, class Allocator, typename Head>
  void resize(::std::vector<T, Allocator>& vector, const Head& head) {
    vector.resize(head);
  }
  template <class T, ::std::size_t N, typename Head>
  void resize([[maybe_unused]] ::std::array<T, N>& array, [[maybe_unused]] const Head& head) {
    assert(array.size() == static_cast<::std::size_t>(head));
  }

  template <class T, class Allocator, typename Head, typename... Tail>
  void resize(::std::vector<T, Allocator>& vector, const Head& head, const Tail&... tail);
  template <class T, ::std::size_t N, typename Head, typename... Tail>
  void resize(::std::array<T, N>& array, const Head& head, const Tail&... tail);

  template <class T, class Allocator, typename Head, typename... Tail>
  void resize(::std::vector<T, Allocator>& vector, const Head& head, const Tail&... tail) {
    vector.resize(head);
    for (auto& child : vector) {
      ::tools::resize(child, tail...);
    }
  }
  template <class T, ::std::size_t N, typename Head, typename... Tail>
  void resize(::std::array<T, N>& array, [[maybe_unused]] const Head& head, const Tail&... tail) {
    assert(array.size() == static_cast<::std::size_t>(head));
    for (auto& child : array) {
      ::tools::resize(child, tail...);
    }
  }
}


#line 1 "tools/fill.hpp"



#include <type_traits>
#line 1 "tools/is_range.hpp"



#line 7 "tools/is_range.hpp"

namespace tools {
  template <typename T, typename = ::std::void_t<>>
  struct is_range : ::std::false_type {};

  template <typename T>
  struct is_range<T, ::std::void_t<decltype(::std::begin(::std::declval<T>()), ::std::end(::std::declval<T>()))>> : ::std::true_type {};

  template <typename T>
  inline constexpr bool is_range_v = ::tools::is_range<T>::value;
}


#line 11 "tools/fill.hpp"

namespace tools {
  template <class T, class Allocator, typename V>
  ::std::enable_if_t<!::tools::is_range_v<T>, void> fill(::std::vector<T, Allocator>& vector, const V& value) {
    ::std::fill(::std::begin(vector), ::std::end(vector), value);
  }
  template <class T, ::std::size_t N, typename V>
  ::std::enable_if_t<!::tools::is_range_v<T>, void> fill(::std::array<T, N>& array, const V& value) {
    ::std::fill(::std::begin(array), ::std::end(array), value);
  }

  template <class T, class Allocator, typename V>
  ::std::enable_if_t<::tools::is_range_v<T>, void> fill(::std::vector<T, Allocator>& vector, const V& value);
  template <class T, ::std::size_t N, typename V>
  ::std::enable_if_t<::tools::is_range_v<T>, void> fill(::std::array<T, N>& array, const V& value);

  template <class T, class Allocator, typename V>
  ::std::enable_if_t<::tools::is_range_v<T>, void> fill(::std::vector<T, Allocator>& vector, const V& value) {
    for (auto& child : vector) {
      ::tools::fill(child, value);
    }
  }
  template <class T, ::std::size_t N, typename V>
  ::std::enable_if_t<::tools::is_range_v<T>, void> fill(::std::array<T, N>& array, const V& value) {
    for (auto& child : array) {
      ::tools::fill(child, value);
    }
  }
}


#line 1 "tools/extend_input.hpp"



// WARNING:
// This file adds functions to std namespace for convenience.
// Strictly speaking, it is not allowed in C++.
// It makes the program ill-formed to include this file, and may cause undefined behavior.

#line 1 "tools/has_mod.hpp"



#line 6 "tools/has_mod.hpp"

namespace tools {
  template <typename T, typename = ::std::void_t<>>
  struct has_mod : ::std::false_type {};

  template <typename T>
  struct has_mod<T, ::std::void_t<decltype(::std::declval<T>().mod())>> : ::std::true_type {};

  template <typename T>
  inline constexpr bool has_mod_v = ::tools::has_mod<T>::value;
}


#line 16 "tools/extend_input.hpp"

namespace tools {
  namespace detail {
    namespace extend_input {
      template <typename T>
      ::std::istream& read(::std::istream& is, T& container) {
        for (auto& v : container) {
          is >> v;
        }
        return is;
      }
    }
  }
}

namespace std {
  template <class T, ::std::size_t N>
  ::std::istream& operator>>(::std::istream& is, ::std::array<T, N>& array) {
    return ::tools::detail::extend_input::read(is, array);
  }

  template <class T1, class T2>
  ::std::istream& operator>>(::std::istream& is, ::std::pair<T1, T2>& pair) {
    return is >> pair.first >> pair.second;
  }

  template <int I = 0, typename... Args>
  ::std::istream& operator>>(::std::istream& is, ::std::tuple<Args...>& tuple) {
    if constexpr (I < int(sizeof...(Args))) {
        is >> ::std::get<I>(tuple);
        return operator>><I + 1>(is, tuple);
      } else {
      return is;
    }
  }

  template <class T, class Allocator>
  ::std::istream& operator>>(::std::istream& is, ::std::vector<T, Allocator>& vector) {
    return ::tools::detail::extend_input::read(is, vector);
  }

  template <typename T>
  ::std::enable_if_t<::tools::has_mod_v<T>, ::std::istream&> operator>>(::std::istream& is, T& x) {
    long long n;
    is >> n;
    x = T(n);
    return is;
  }
}


#line 1 "tools/extend_output.hpp"



// WARNING:
// This file adds functions to std namespace for convenience.
// Strictly speaking, it is not allowed in C++.
// It makes the program ill-formed to include this file, and may cause undefined behavior.

#line 12 "tools/extend_output.hpp"
#include <optional>
#line 24 "tools/extend_output.hpp"

namespace tools {
  namespace detail {
    namespace extend_output {
      template <typename T>
      ::std::ostream& debug_print(::std::ostream& os, const T& container) {
        ::std::string delimiter = "";
        os << '[';
        for (const auto& v : container) {
          os << delimiter << v;
          delimiter = ", ";
        }
        os << ']';
        return os;
      }
    }
  }
}

namespace std {
  template <class T, ::std::size_t N>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::array<T, N>& array) {
    return ::tools::detail::extend_output::debug_print(os, array);
  }
  
  template <class Key, class T, class Compare, class Allocator>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::map<Key, T, Compare, Allocator>& map) {
    return ::tools::detail::extend_output::debug_print(os, map);
  }

  template <typename T>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::optional<T>& optional) {
    if (optional) {
      return os << *optional;
    } else {
      return os << "null";
    }
  }
  
  template <class T1, class T2>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::pair<T1, T2>& pair) {
    return os << '[' << pair.first << ", " << pair.second << ']';
  }
  
  template <class T, class Container>
  ::std::ostream& operator<<(::std::ostream& os, ::std::queue<T, Container>& queue) {
    ::std::queue<T, Container> other = queue;
    ::std::string delimiter = "";
    os << '[';
    while (!queue.empty()) {
      os << delimiter << queue.front();
      delimiter = ", ";
      queue.pop();
    }
    os << ']';
  
    queue = ::std::move(other);
    return os;
  }
  
  template <class Key, class Compare, class Allocator>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::set<Key, Compare, Allocator>& set) {
    return ::tools::detail::extend_output::debug_print(os, set);
  }

  template <class T, class Container>
  ::std::ostream& operator<<(::std::ostream& os, ::std::stack<T, Container>& stack) {
    ::std::stack<T, Container> other;
    while (!stack.empty()) {
      other.push(stack.top());
      stack.pop();
    }
  
    ::std::string delimiter = "";
    os << '[';
    while (!other.empty()) {
      os << delimiter << other.top();
      delimiter = ", ";
      stack.push(other.top());
      other.pop();
    }
    os << ']';
  
    return os;
  }
  
  template <int I = -1, typename... Args>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::tuple<Args...>& tuple) {
    if constexpr (I == -1) {
      os << '[';
    } else if constexpr (I == int(sizeof...(Args))) {
      os << ']';
    } else if constexpr (I == 0) {
      os << ::std::get<I>(tuple);
    } else {
      os << ", " << ::std::get<I>(tuple);
    }
  
    if constexpr (I < int(sizeof...(Args))) {
      return operator<<<I + 1>(os, tuple);
    } else {
      return os;
    }
  }
  
  template <class Key, class T, class Hash, class Pred, class Allocator>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::unordered_map<Key, T, Hash, Pred, Allocator>& unordered_map) {
    return ::tools::detail::extend_output::debug_print(os, unordered_map);
  }
  
  template <class Key, class Hash, class Pred, class Allocator>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::unordered_set<Key, Hash, Pred, Allocator>& unordered_set) {
    return ::tools::detail::extend_output::debug_print(os, unordered_set);
  }
  
  template <class T, class Allocator>
  ::std::ostream& operator<<(::std::ostream& os, const ::std::vector<T, Allocator>& vector) {
    return ::tools::detail::extend_output::debug_print(os, vector);
  }
  
  template <typename T>
  ::std::enable_if_t<::tools::has_mod_v<T>, ::std::ostream&> operator<<(::std::ostream& os, const T& x) {
    return os << x.val();
  }
}


#line 1 "tools/extend_hash.hpp"



// WARNING:
// This file adds partial specializations for classes in std namespace, for convenience.
// Strictly speaking, it is not allowed in C++.
// It makes the program ill-formed to include this file, and may cause undefined behavior.

#line 1 "tools/tuple_hash.hpp"



#line 1 "tools/now.hpp"



#line 5 "tools/now.hpp"

namespace tools {
  inline long long now() {
    return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
  }
}


#line 1 "tools/hash_combine.hpp"



#line 6 "tools/hash_combine.hpp"

// Source: https://github.com/google/cityhash/blob/f5dc54147fcce12cefd16548c8e760d68ac04226/src/city.h
// License: MIT
// Author: Google Inc.

// Copyright (c) 2011 Google, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

namespace tools {
  template <typename T>
  void hash_combine(::std::size_t& seed, const T& v) {
    static const ::std::hash<T> hasher;
    static constexpr ::std::size_t k_mul = 0x9ddfea08eb382d69ULL;
    ::std::size_t a = (hasher(v) ^ seed) * k_mul;
    a ^= (a >> 47);
    ::std::size_t b = (seed ^ a) * k_mul;
    b ^= (b >> 47);
    seed = b * k_mul;
  }
}


#line 11 "tools/tuple_hash.hpp"

namespace tools {
  template <typename... Ts>
  struct tuple_hash {
    template <::std::size_t I = sizeof...(Ts) - 1>
    ::std::size_t operator()(const ::std::tuple<Ts...>& key) const {
      if constexpr (I == ::std::numeric_limits<::std::size_t>::max()) {
        static const ::std::size_t seed = ::tools::now();
        return seed;
      } else {
        ::std::size_t seed = this->operator()<I - 1>(key);
        ::tools::hash_combine(seed, ::std::get<I>(key));
        return seed;
      }
    }
  };
}


#line 14 "tools/extend_hash.hpp"

namespace std {
  template <class T1, class T2>
  struct hash<::std::pair<T1, T2>> {
    ::std::size_t operator()(const ::std::pair<T1, T2>& key) const {
      static const ::tools::tuple_hash<T1, T2> hasher;
      return hasher(::std::make_tuple(key.first, key.second));
    }
  };

  template <class... Args>
  struct hash<::std::tuple<Args...>> {
    ::std::size_t operator()(const ::std::tuple<Args...>& key) const {
      static const ::tools::tuple_hash<Args...> hasher;
      return hasher(key);
    }
  };
}


#line 23 "tools/util.hpp"

using ll = long long;
using ull = unsigned long long;
using i32 = ::std::int32_t;
using u32 = ::std::uint32_t;
using i64 = ::std::int64_t;
using u64 = ::std::uint64_t;

#define ALL(x) ::std::begin(x), ::std::end(x)
#define REP(i, n) for (long long i = 0, i##_len = static_cast<long long>(n); i < i##_len; ++i)
Back to top page