utility/fast_io.cpp

• View this file on GitHub
• Last update: 2022-01-28 13:07:07+09:00

Depends on

• internal/enable_avx2.cpp
• utility/int_alias.cpp
• utility/rep.cpp
• utility/revrep.cpp

Verified with

• test/fast_io.test.cpp

Code

#pragma once
#include <cstdio>
#include <cstring>
#include <type_traits>
#include <utility>
#include "../internal/enable_avx2.cpp"
#include "int_alias.cpp"
#include "rep.cpp"
#include "revrep.cpp"

namespace fast_io {

template <u64 N> constexpr u64 TEN = 10 * TEN<N - 1>;
template <> constexpr u64 TEN<0> = 1;

constexpr int BUF_SIZE = 1 << 17;

TARGET_AVX2 inline constexpr int integer_digits(const u64 n) {
    if (n >= TEN<10>) {
        if (n >= TEN<15>) {
            if (n >= TEN<19>) return 20;
            if (n >= TEN<18>) return 19;
            if (n >= TEN<17>) return 18;
            if (n >= TEN<16>) return 17;
            return 16;
        } else {
            if (n >= TEN<14>) return 15;
            if (n >= TEN<13>) return 14;
            if (n >= TEN<12>) return 13;
            if (n >= TEN<11>) return 12;
            return 11;
        }
    } else {
        if (n >= TEN<5>) {
            if (n >= TEN<9>) return 10;
            if (n >= TEN<8>) return 9;
            if (n >= TEN<7>) return 8;
            if (n >= TEN<6>) return 7;
            return 6;
        } else {
            if (n >= TEN<4>) return 5;
            if (n >= TEN<3>) return 4;
            if (n >= TEN<2>) return 3;
            if (n >= TEN<1>) return 2;
            return 1;
        }
    }
}

struct NumBlock {
    char NUM[40000];
    constexpr NumBlock() : NUM() {
        for (const int i : rep(0, 10000)) {
            int n = i;
            for (const int j : revrep(0, 4)) {
                NUM[i * 4 + j] = n % 10 + '0';
                n /= 10;
            }
        }
    }
} constexpr num_block;

class Scanner {
    char buf[BUF_SIZE];
    int left, right;

    TARGET_AVX2 inline void load() {
        const int len = right - left;
        std::memcpy(buf, buf + left, len);
        right = len + std::fread(buf + len, 1, BUF_SIZE - len, stdin);
        left = 0;
    }

    TARGET_AVX2 inline void ignore_spaces() {
        while (buf[left] <= ' ') {
            if (__builtin_expect(++left == right, 0)) load();
        }
    }

  public:
    Scanner() : buf(), left(0), right(0) { load(); }

    TARGET_AVX2 void scan(char& c) {
        ignore_spaces();
        c = buf[left++];
    }

    template <typename T, std::enable_if_t<std::is_integral_v<T>>* = nullptr> TARGET_AVX2 inline void scan(T& x) {
        ignore_spaces();
        if (__builtin_expect(left + 32 > right, 0)) load();
        char c = buf[left++];
        bool minus = false;
        if constexpr (std::is_signed_v<T>) {
            if (c == '-') {
                minus = 1;
                c = buf[left++];
            }
        }
        x = 0;
        while (c >= '0') {
            x = x * 10 + (c & 15);
            c = buf[left++];
        }
        if constexpr (std::is_signed_v<T>) {
            if (minus) x = -x;
        }
    }

    template <class T, class... Args> TARGET_AVX2 inline void scan(T& x, Args&... args) {
        scan(x);
        scan(args...);
    }
};

class Printer {
    char buf[BUF_SIZE];
    int pos;

    TARGET_AVX2 inline void flush() {
        std::fwrite(buf, 1, pos, stdout);
        pos = 0;
    }

  public:
    Printer() : buf(), pos(0) {}
    ~Printer() { flush(); }

    TARGET_AVX2 void print(const char c) {
        buf[pos] = c;
        if (__builtin_expect(++pos == BUF_SIZE, 0)) flush();
    }

    template <typename T, std::enable_if_t<std::is_integral_v<T>>* = nullptr> TARGET_AVX2 inline void print(T x) {
        if (__builtin_expect(pos + 32 > BUF_SIZE, 0)) flush();
        if (x == 0) {
            buf[pos++] = '0';
            return;
        }
        if constexpr (std::is_signed_v<T>) {
            if (x < 0) {
                buf[pos++] = '-';
                x = -x;
            }
        }
        const int digit = integer_digits(x);
        int len = digit;
        while (len >= 4) {
            len -= 4;
            std::memcpy(buf + pos + len, num_block.NUM + (x % 10000) * 4, 4);
            x /= 10000;
        }
        std::memcpy(buf + pos, num_block.NUM + x * 4 + 4 - len, len);
        pos += digit;
    }

    template <class T, class... Args> TARGET_AVX2 inline void print(T x, Args&&... args) {
        print(x);
        print(' ');
        print(std::forward<Args>(args)...);
    }

    template <class... Args> TARGET_AVX2 void println(Args&&... args) {
        print(std::forward<Args>(args)...);
        print('\n');
    }
};

};  // namespace fast_io

#line 2 "utility/fast_io.cpp"
#include <cstdio>
#include <cstring>
#include <type_traits>
#include <utility>
#line 2 "internal/enable_avx2.cpp"

#ifdef ENABLE_AVX2
#define TARGET_AVX2 __attribute__((target("avx2")))
#else
#define TARGET_AVX2
#endif
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 2 "utility/rep.cpp"
#include <algorithm>

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 3 "utility/revrep.cpp"

class ReversedRange {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { --itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr ReversedRange(const int first, const int last) noexcept
        : first(last - 1), last(std::min(first, last) - 1) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr ReversedRange revrep(const int l, const int r) noexcept { return ReversedRange(l, r); }
constexpr ReversedRange revrep(const int n) noexcept { return ReversedRange(0, n); }
#line 10 "utility/fast_io.cpp"

namespace fast_io {

template <u64 N> constexpr u64 TEN = 10 * TEN<N - 1>;
template <> constexpr u64 TEN<0> = 1;

constexpr int BUF_SIZE = 1 << 17;

TARGET_AVX2 inline constexpr int integer_digits(const u64 n) {
    if (n >= TEN<10>) {
        if (n >= TEN<15>) {
            if (n >= TEN<19>) return 20;
            if (n >= TEN<18>) return 19;
            if (n >= TEN<17>) return 18;
            if (n >= TEN<16>) return 17;
            return 16;
        } else {
            if (n >= TEN<14>) return 15;
            if (n >= TEN<13>) return 14;
            if (n >= TEN<12>) return 13;
            if (n >= TEN<11>) return 12;
            return 11;
        }
    } else {
        if (n >= TEN<5>) {
            if (n >= TEN<9>) return 10;
            if (n >= TEN<8>) return 9;
            if (n >= TEN<7>) return 8;
            if (n >= TEN<6>) return 7;
            return 6;
        } else {
            if (n >= TEN<4>) return 5;
            if (n >= TEN<3>) return 4;
            if (n >= TEN<2>) return 3;
            if (n >= TEN<1>) return 2;
            return 1;
        }
    }
}

struct NumBlock {
    char NUM[40000];
    constexpr NumBlock() : NUM() {
        for (const int i : rep(0, 10000)) {
            int n = i;
            for (const int j : revrep(0, 4)) {
                NUM[i * 4 + j] = n % 10 + '0';
                n /= 10;
            }
        }
    }
} constexpr num_block;

class Scanner {
    char buf[BUF_SIZE];
    int left, right;

    TARGET_AVX2 inline void load() {
        const int len = right - left;
        std::memcpy(buf, buf + left, len);
        right = len + std::fread(buf + len, 1, BUF_SIZE - len, stdin);
        left = 0;
    }

    TARGET_AVX2 inline void ignore_spaces() {
        while (buf[left] <= ' ') {
            if (__builtin_expect(++left == right, 0)) load();
        }
    }

  public:
    Scanner() : buf(), left(0), right(0) { load(); }

    TARGET_AVX2 void scan(char& c) {
        ignore_spaces();
        c = buf[left++];
    }

    template <typename T, std::enable_if_t<std::is_integral_v<T>>* = nullptr> TARGET_AVX2 inline void scan(T& x) {
        ignore_spaces();
        if (__builtin_expect(left + 32 > right, 0)) load();
        char c = buf[left++];
        bool minus = false;
        if constexpr (std::is_signed_v<T>) {
            if (c == '-') {
                minus = 1;
                c = buf[left++];
            }
        }
        x = 0;
        while (c >= '0') {
            x = x * 10 + (c & 15);
            c = buf[left++];
        }
        if constexpr (std::is_signed_v<T>) {
            if (minus) x = -x;
        }
    }

    template <class T, class... Args> TARGET_AVX2 inline void scan(T& x, Args&... args) {
        scan(x);
        scan(args...);
    }
};

class Printer {
    char buf[BUF_SIZE];
    int pos;

    TARGET_AVX2 inline void flush() {
        std::fwrite(buf, 1, pos, stdout);
        pos = 0;
    }

  public:
    Printer() : buf(), pos(0) {}
    ~Printer() { flush(); }

    TARGET_AVX2 void print(const char c) {
        buf[pos] = c;
        if (__builtin_expect(++pos == BUF_SIZE, 0)) flush();
    }

    template <typename T, std::enable_if_t<std::is_integral_v<T>>* = nullptr> TARGET_AVX2 inline void print(T x) {
        if (__builtin_expect(pos + 32 > BUF_SIZE, 0)) flush();
        if (x == 0) {
            buf[pos++] = '0';
            return;
        }
        if constexpr (std::is_signed_v<T>) {
            if (x < 0) {
                buf[pos++] = '-';
                x = -x;
            }
        }
        const int digit = integer_digits(x);
        int len = digit;
        while (len >= 4) {
            len -= 4;
            std::memcpy(buf + pos + len, num_block.NUM + (x % 10000) * 4, 4);
            x /= 10000;
        }
        std::memcpy(buf + pos, num_block.NUM + x * 4 + 4 - len, len);
        pos += digit;
    }

    template <class T, class... Args> TARGET_AVX2 inline void print(T x, Args&&... args) {
        print(x);
        print(' ');
        print(std::forward<Args>(args)...);
    }

    template <class... Args> TARGET_AVX2 void println(Args&&... args) {
        print(std::forward<Args>(args)...);
        print('\n');
    }
};

};  // namespace fast_io

Back to top page