template/in.hpp

View this file on GitHub
Last update: 2024-06-30 13:01:18+09:00
Include: #include "template/in.hpp"

Depends on

Required by

Verified with

Code

#pragma once
#include "alias.hpp"
#include "type-traits.hpp"
namespace fastio {
template <std::size_t BUFF_SIZE = 1 << 17, int decimal_precision = 16>
struct Scanner {
   private:
    template <typename, typename = void>
    struct has_scan : std::false_type {};
    template <class T>
    struct has_scan<T, decltype(std::declval<T>().scan(std::declval<Scanner&>()), (void)0)> : std::true_type {};
    FILE* file;
    char buffer[BUFF_SIZE + 1];
    int idx, sz;
    bool state;
    inline void load() {
        int len = sz - idx;
        if (idx < len) return;
        memcpy(buffer, buffer + idx, len);
        sz = len + fread(buffer + len, 1, BUFF_SIZE - len, file);
        idx = 0;
        if (static_cast<size_t>(sz) < BUFF_SIZE) buffer[sz++] = '\n';
    }
    inline char cur() {
        if (idx == sz) load();
        if (idx == sz) {
            state = false;
            return '\0';
        }
        return buffer[idx];
    }
    inline void next() {
        if (idx == sz) load();
        if (idx == sz) return;
        idx++;
    }

   public:
    Scanner() : Scanner(stdin) {}
    explicit Scanner(FILE* file) : file(file), idx(0), sz(0), state(true) { load(); }
    ~Scanner() {
        if (file != stdin) fclose(file);
    }

    inline char scan_char() {
        if (idx == sz) load();
        return (idx == sz ? '\0' : buffer[idx++]);
    }
    Scanner ignore(int n = 1) {
        if (idx + n > sz) load();
        idx += n;
        return (*this);
    }
    inline void skip_space() {
        if (idx == sz) load();
        while (('\t' <= cur() && cur() <= '\r') || cur() == ' ') {
            next();
        }
    }
    void scan(char& a) {
        skip_space();
        a = scan_char();
    }
    void scan(std::string& a) {
        skip_space();
        a.clear();
        while (cur() != '\0' && (buffer[idx] < '\t' || '\r' < buffer[idx]) && buffer[idx] != ' ') {
            a += scan_char();
        }
    }
    template <std::size_t len>
    void scan(std::bitset<len>& a) {
        skip_space();
        if (idx + len > sz) load();
        rrep(i, len) a[i] = (buffer[idx++] != '0');
    }
    template <typename T, typename std::enable_if<is_int<T>::value && !has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        skip_space();
        bool neg = false;
        if constexpr (std::is_signed<T>::value || std::is_same_v<T, __int128_t>) {
            if (cur() == '-') {
                neg = true;
                next();
            }
        }
        if (idx + 40 > sz && (idx == sz || ('0' <= buffer[sz - 1] && buffer[sz - 1] <= '9'))) load();
        a = 0;
        while ('0' <= buffer[idx] && buffer[idx] <= '9') {
            a = a * 10 + (buffer[idx++] & 15);
        }
        if constexpr (std::is_signed<T>::value || std::is_same<T, __int128_t>::value) {
            if (neg) a = -a;
        }
    }
    template <typename T, typename std::enable_if<std::is_floating_point<T>::value && !has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        skip_space();
        bool neg = false;
        if (cur() == '-') {
            neg = true;
            next();
        }
        a = 0;
        while ('0' <= cur() && cur() <= '9') {
            a = a * 10 + (scan_char() & 15);
        }
        if (cur() == '.') {
            next();
            T n = 0, d = 1;
            for (int i = 0; '0' <= cur() && cur() <= '9' && i < decimal_precision; ++i) {
                n = n * 10 + (scan_char() & 15);
                d *= 10;
            }
            while ('0' <= cur() && cur() <= '9') next();
            a += n / d;
        }
        if (neg) a = -a;
    }

   private:
    template <std::size_t i, typename... Args>
    void scan(std::tuple<Args...>& a) {
        if constexpr (i < sizeof...(Args)) {
            scan(std::get<i>(a));
            scan<i + 1, Args...>(a);
        }
    }

   public:
    template <typename... Args>
    void scan(std::tuple<Args...>& a) {
        scan<0, Args...>(a);
    }
    template <typename T, typename U>
    void scan(std::pair<T, U>& a) {
        scan(a.first);
        scan(a.second);
    }
    template <typename T, typename std::enable_if<is_range<T>::value && !has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        for (auto& i : a) scan(i);
    }
    template <typename T, typename std::enable_if<has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        a.scan(*this);
    }
    void operator()() {}
    template <typename Head, typename... Tail>
    void operator()(Head& head, Tail&... tail) {
        scan(head);
        operator()(std::forward<Tail&>(tail)...);
    }
    template <typename T>
    Scanner& operator>>(T& a) {
        scan(a);
        return *this;
    }
    explicit operator bool() const { return state; }
    friend Scanner& getline(Scanner& sc, std::string& a) {
        a.clear();
        char c;
        if ((c = sc.scan_char()) == '\0' || c == '\n') return sc;
        a += c;
        while ((c = sc.scan_char()) != '\0' && c != '\n') a += c;
        return sc;
    }
};
Scanner<> sc;
}  // namespace fastio
using fastio::sc;

#line 2 "template/alias.hpp"
#include <bits/stdc++.h>

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using u128 = __uint128_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vs = std::vector<std::string>;
using vc = std::vector<char>;
using vvl = std::vector<vl>;
using vd = std::vector<double>;
using vp = std::vector<pl>;
using vb = std::vector<bool>;
template <typename T>
struct infinity {
    static constexpr T max = std::numeric_limits<T>::max();
    static constexpr T min = std::numeric_limits<T>::min();
    static constexpr T value = std::numeric_limits<T>::max() / 2;
    static constexpr T mvalue = std::numeric_limits<T>::min() / 2;
};
template <typename T>
constexpr T INF = infinity<T>::value;
constexpr ll inf = INF<ll>;
constexpr ld EPS = 1e-8;
constexpr ld PI = 3.1415926535897932384626;
constexpr int dx[8] = {-1, 0, 1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
#line 3 "template/type-traits.hpp"

#line 3 "template/macro.hpp"

#ifndef __COUNTER__
#define __COUNTER__ __LINE__
#endif

#define SELECT4(a, b, c, d, e, ...) e
#define SELECT3(a, b, c, d, ...) d
#define REP_1(a, c) for (ll REP_##c = 0; REP_##c < (ll)(a); ++REP_##c)
#define REP1(a) REP_1(a, __COUNTER__)
#define REP2(i, a) for (ll i = 0; i < (ll)(a); ++i)
#define REP3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define REP4(i, a, b, c) for (ll i = (ll)(a); i < (ll)(b); i += (ll)(c))
#define rep(...) SELECT4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP_1(a, c) for (ll RREP_##c = (ll)(a) - 1; RREP_##c >= 0; --RREP_##c)
#define RREP1(a) RREP_1(a, __COUNTER__)
#define RREP2(i, a) for (ll i = (ll)(a) - 1; i >= 0; --i)
#define RREP3(i, a, b) for (ll i = (ll)(b) - 1; i >= (ll)(a); --i)
#define rrep(...) SELECT3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__)
#define all(v) std::begin(v), std::end(v)
#define rall(v) std::rbegin(v), std::rend(v)
#define INT(...)     \
    int __VA_ARGS__; \
    scan(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    scan(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    scan(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    scan(__VA_ARGS__)
#define DBL(...)        \
    double __VA_ARGS__; \
    scan(__VA_ARGS__)
#define LD(...)     \
    ld __VA_ARGS__; \
    scan(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#line 5 "template/type-traits.hpp"

template <typename T, typename... Args>
struct function_traits_impl {
    using return_type = T;
    static constexpr std::size_t arg_size = sizeof...(Args);
    template <std::size_t idx>
    using argument_type = typename std::tuple_element<idx, std::tuple<Args...>>::type;
    using argument_types = std::tuple<Args...>;
};

template <typename>
struct function_traits_helper;
template <typename T, typename Tp, typename... Args>
struct function_traits_helper<T (Tp::*)(Args...)> : function_traits_impl<T, Args...> {};
template <typename T, typename Tp, typename... Args>
struct function_traits_helper<T (Tp::*)(Args...) const> : function_traits_impl<T, Args...> {};
template <typename T, typename Tp, typename... Args>
struct function_traits_helper<T (Tp::*)(Args...)&> : function_traits_impl<T, Args...> {};
template <typename T, typename Tp, typename... Args>
struct function_traits_helper<T (Tp::*)(Args...) const&> : function_traits_impl<T, Args...> {};

template <typename F>
using function_traits = function_traits_helper<decltype(&std::remove_reference<F>::type::operator())>;
template <typename F>
using function_return_type = typename function_traits<F>::return_type;
template <typename F, std::size_t idx>
using function_argument_type = typename function_traits<F>::template argument_type<idx>;
template <typename F>
using function_argument_types = typename function_traits<F>::argument_types;
template <class T>
using is_signed_int = std::integral_constant<bool, (std::is_integral<T>::value && std::is_signed<T>::value) || std::is_same<T, __int128_t>::value>;
template <class T>
using is_unsigned_int = std::integral_constant<bool, (std::is_integral<T>::value && std::is_unsigned<T>::value) || std::is_same<T, __uint128_t>::value>;
template <class T>
using is_int = std::integral_constant<bool, is_signed_int<T>::value || is_unsigned_int<T>::value>;
template <typename T, typename = void>
struct is_range : std::false_type {};
template <typename T>
struct is_range<
    T,
    decltype(all(std::declval<typename std::add_lvalue_reference<T>::type>()), (void)0)> : std::true_type {};
template <std::size_t size>
struct int_least {
    static_assert(size <= 128, "size must be less than or equal to 128");
    using type = typename std::conditional<
        size <= 8, std::int_least8_t,
        typename std::conditional<
            size <= 16, std::int_least16_t,
            typename std::conditional<
                size <= 32, std::int_least32_t,
                typename std::conditional<size <= 64, std::int_least64_t, __int128_t>::type>::type>::type>::type;
};
template <std::size_t size>
using int_least_t = typename int_least<size>::type;
template <std::size_t size>
struct uint_least {
    static_assert(size <= 128, "size must be less than or equal to 128");
    using type = typename std::conditional<
        size <= 8, std::uint_least8_t,
        typename std::conditional<
            size <= 16, std::uint_least16_t,
            typename std::conditional<
                size <= 32, std::uint_least32_t,
                typename std::conditional<size <= 64, std::uint_least64_t, __uint128_t>::type>::type>::type>::type;
};
template <std::size_t size>
using uint_least_t = typename uint_least<size>::type;
template <typename T>
using double_size_int = int_least<std::numeric_limits<T>::digits * 2 + 1>;
template <typename T>
using double_size_int_t = typename double_size_int<T>::type;
template <typename T>
using double_size_uint = uint_least<std::numeric_limits<T>::digits * 2>;
template <typename T>
using double_size_uint_t = typename double_size_uint<T>::type;
template <typename T>
using double_size = typename std::conditional<std::is_signed<T>::value, double_size_int<T>, double_size_uint<T>>::type;
template <typename T>
using double_size_t = typename double_size<T>::type;
#line 4 "template/in.hpp"
namespace fastio {
template <std::size_t BUFF_SIZE = 1 << 17, int decimal_precision = 16>
struct Scanner {
   private:
    template <typename, typename = void>
    struct has_scan : std::false_type {};
    template <class T>
    struct has_scan<T, decltype(std::declval<T>().scan(std::declval<Scanner&>()), (void)0)> : std::true_type {};
    FILE* file;
    char buffer[BUFF_SIZE + 1];
    int idx, sz;
    bool state;
    inline void load() {
        int len = sz - idx;
        if (idx < len) return;
        memcpy(buffer, buffer + idx, len);
        sz = len + fread(buffer + len, 1, BUFF_SIZE - len, file);
        idx = 0;
        if (static_cast<size_t>(sz) < BUFF_SIZE) buffer[sz++] = '\n';
    }
    inline char cur() {
        if (idx == sz) load();
        if (idx == sz) {
            state = false;
            return '\0';
        }
        return buffer[idx];
    }
    inline void next() {
        if (idx == sz) load();
        if (idx == sz) return;
        idx++;
    }

   public:
    Scanner() : Scanner(stdin) {}
    explicit Scanner(FILE* file) : file(file), idx(0), sz(0), state(true) { load(); }
    ~Scanner() {
        if (file != stdin) fclose(file);
    }

    inline char scan_char() {
        if (idx == sz) load();
        return (idx == sz ? '\0' : buffer[idx++]);
    }
    Scanner ignore(int n = 1) {
        if (idx + n > sz) load();
        idx += n;
        return (*this);
    }
    inline void skip_space() {
        if (idx == sz) load();
        while (('\t' <= cur() && cur() <= '\r') || cur() == ' ') {
            next();
        }
    }
    void scan(char& a) {
        skip_space();
        a = scan_char();
    }
    void scan(std::string& a) {
        skip_space();
        a.clear();
        while (cur() != '\0' && (buffer[idx] < '\t' || '\r' < buffer[idx]) && buffer[idx] != ' ') {
            a += scan_char();
        }
    }
    template <std::size_t len>
    void scan(std::bitset<len>& a) {
        skip_space();
        if (idx + len > sz) load();
        rrep(i, len) a[i] = (buffer[idx++] != '0');
    }
    template <typename T, typename std::enable_if<is_int<T>::value && !has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        skip_space();
        bool neg = false;
        if constexpr (std::is_signed<T>::value || std::is_same_v<T, __int128_t>) {
            if (cur() == '-') {
                neg = true;
                next();
            }
        }
        if (idx + 40 > sz && (idx == sz || ('0' <= buffer[sz - 1] && buffer[sz - 1] <= '9'))) load();
        a = 0;
        while ('0' <= buffer[idx] && buffer[idx] <= '9') {
            a = a * 10 + (buffer[idx++] & 15);
        }
        if constexpr (std::is_signed<T>::value || std::is_same<T, __int128_t>::value) {
            if (neg) a = -a;
        }
    }
    template <typename T, typename std::enable_if<std::is_floating_point<T>::value && !has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        skip_space();
        bool neg = false;
        if (cur() == '-') {
            neg = true;
            next();
        }
        a = 0;
        while ('0' <= cur() && cur() <= '9') {
            a = a * 10 + (scan_char() & 15);
        }
        if (cur() == '.') {
            next();
            T n = 0, d = 1;
            for (int i = 0; '0' <= cur() && cur() <= '9' && i < decimal_precision; ++i) {
                n = n * 10 + (scan_char() & 15);
                d *= 10;
            }
            while ('0' <= cur() && cur() <= '9') next();
            a += n / d;
        }
        if (neg) a = -a;
    }

   private:
    template <std::size_t i, typename... Args>
    void scan(std::tuple<Args...>& a) {
        if constexpr (i < sizeof...(Args)) {
            scan(std::get<i>(a));
            scan<i + 1, Args...>(a);
        }
    }

   public:
    template <typename... Args>
    void scan(std::tuple<Args...>& a) {
        scan<0, Args...>(a);
    }
    template <typename T, typename U>
    void scan(std::pair<T, U>& a) {
        scan(a.first);
        scan(a.second);
    }
    template <typename T, typename std::enable_if<is_range<T>::value && !has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        for (auto& i : a) scan(i);
    }
    template <typename T, typename std::enable_if<has_scan<T>::value>::type* = nullptr>
    void scan(T& a) {
        a.scan(*this);
    }
    void operator()() {}
    template <typename Head, typename... Tail>
    void operator()(Head& head, Tail&... tail) {
        scan(head);
        operator()(std::forward<Tail&>(tail)...);
    }
    template <typename T>
    Scanner& operator>>(T& a) {
        scan(a);
        return *this;
    }
    explicit operator bool() const { return state; }
    friend Scanner& getline(Scanner& sc, std::string& a) {
        a.clear();
        char c;
        if ((c = sc.scan_char()) == '\0' || c == '\n') return sc;
        a += c;
        while ((c = sc.scan_char()) != '\0' && c != '\n') a += c;
        return sc;
    }
};
Scanner<> sc;
}  // namespace fastio
using fastio::sc;