제출 #917447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917447		nguyen31hoang08minh2003	Sateliti (COCI20_satellti)	C++17	10 / 110	48 ms	44368 KiB

Main

#include <bits/stdc++.h>

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

class SignedBigInteger {
protected:

    const static int BASE = 1E7;
    const static int BASE_DIGIT_COUNT = 7;

    static long long convertStringToInteger(const std::string &s) {
        long long result;
        std::stringstream value(s);
        value >> result;
        return result;
    }

    static std::string convertIntegerToString(const long long x) {
        std::stringstream value;
        std::string result;
        value << x;
        value >> result;
        return result;
    }

    static std::string findSubstring(const std::string &s, int l, const int r) {
        if (l < 0)
            l = 0;
        return s.substr(l, r - l + 1);
    }

    static std::vector<long long> addDigits(std::vector<long long> a, const std::vector<long long> &b) {
        const int lengthA = a.size(), lengthB = b.size();
        a.resize(std::max(lengthA, lengthB));
        for (int i = 0; i < lengthB; ++i)
            a[i] += b[i];
        return a;
    }

    static std::vector<long long> subtractDigits(std::vector<long long> a, const std::vector<long long> &b) {
        /**

            a >= b

        **/
        long long remainder = 0;

        const int lengthA = a.size(), lengthB = b.size();

        for (int i = 0; i < lengthB; ++i) {
            remainder = a[i] - b[i] - remainder;
            if (remainder < 0) {
                a[i] = remainder + BASE;
                remainder = 1;
            } else {
                a[i] = remainder;
                remainder = 0;
            }
        }

        for (int i = lengthB; i < lengthA; ++i) {
            remainder = a[i] - remainder;
            if (remainder < 0) {
                a[i] = remainder + BASE;
                remainder = 1;
            } else {
                a[i] = remainder;
                remainder = 0;
            }
        }

        return a;
    }


    static int getReversedBits(int const mask, int const n) {
        int result(0);
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i))
                result |= 1 << n - 1 - i;
        return result;
    }

    static int checkPowerOfTwo(int number) {
        for (; !(number & 1); number >>= 1);
        return number == 1;
    }

    static int getNumberOfBits(int number) {
        if (number == 0)
            return 1;
        int result{};
        for (; number; number >>= 1)
            ++result;
        return result;
    }

    static void fft(std::vector<std::complex<long double> > &p, bool const invert) {
        const int length(p.size());
        if (length == 1)
            return;
        const int n(getNumberOfBits(length - 1));
        std::vector<std::complex<long double> > next(length), w(length);
        std::complex<long double> u, v;
        long double angle;
        for (int x = 0, y; x < length; ++x) {
            y = getReversedBits(x, n);
            if (x < y)
                swap(p[x], p[y]);
        }
        w.front() = 1;
        for (int i, even, odd, span = 1; span < length; span <<= 1) {
            angle = acos(-1) / span;
            if (invert)
                angle = -angle;
            const std::complex<long double> aug(cos(angle), sin(angle));
            for (i = 1; i < span; ++i)
                w[i] = w[i - 1] * aug;
            for (even = 0, odd = span; even < length;) {
                for (i = 0; i < span; ++i) {
                    u = p[even + i];
                    v = p[odd + i] * w[i];
                    next[even + i] = u + v;
                    next[odd + i] = u - v;
                }
                even = odd + span;
                odd = even + span;
            };
            for (i = 0; i < length; ++i)
                p[i] = next[i];
        }
        if (invert) {
            for (int i = 0; i < length; ++i)
                p[i] /= length;
        }
    }

    static void multiplyPolynomials(std::vector<long double> const &a, std::vector<long double> const &b, std::vector<long double> &result) {
        const int lengthA(a.size()), lengthB(b.size()), length(lengthA + lengthB);
        std::vector<std::complex<long double> > fa(a.begin(), a.end()), fb(b.begin(), b.end());
        int n = 1;
        for (; n < length; n <<= 1);
        fa.resize(n);
        fb.resize(n);
        fft(fa, false);
        fft(fb, false);
        for (int i = 0; i < n; ++i)
            fa[i] *= fb[i];
        fft(fa, true);
        result.resize(n);
        for (int i = 0; i < n; ++i)
            result[i] = round(fa[i].real());
    }

    static void multiplyPolynomials(std::vector<long long> const &a, std::vector<long long> const &b, std::vector<long long> &result) {
        const int lengthA(a.size()), lengthB(b.size()), length(lengthA + lengthB - 1);
        std::vector<std::complex<long double> > fa(a.begin(), a.end()), fb(b.begin(), b.end());
        int n = 1;
        for (; n < length; n <<= 1);
        fa.resize(n);
        fb.resize(n);
        fft(fa, false);
        fft(fb, false);
        for (int i = 0; i < n; ++i)
            fa[i] *= fb[i];
        fft(fa, true);
        result.resize(length);
        for (int i = 0; i < length; ++i)
            result[i] = round(fa[i].real());
    }

private:

    bool negative;
    std::vector<long long> digits;

    void fixInteger() {
        long long remainder = 0;
        for (long long &i : digits) {
            remainder += i;
            i = remainder % BASE;
            remainder /= BASE;
        }
        for (; remainder; remainder /= BASE)
            digits.push_back(remainder % BASE);
        while (digits.size() > 1 && !digits.back())
            digits.pop_back();
        if (digits.size() == 1 && digits.front() == 0)
            negative = false;
    }

public:

    SignedBigInteger(): negative(false), digits(1, 0) {};

    SignedBigInteger(const std::string &s) {
        if (s.empty())
            throw std::invalid_argument("The argument must be non-empty");
        const int length = s.size();
        if (s.front() == '-') {
            if (length == 1)
                throw std::invalid_argument("The argument must contain at least one digit");
            negative = true;
            for (int i = length - 1; i >= 1; i -= BASE_DIGIT_COUNT)
                digits.push_back(convertStringToInteger(findSubstring(s, std::max(i - BASE_DIGIT_COUNT + 1, 1), i)));
        } else {
            negative = false;
            for (int i = length - 1; i >= 0; i -= BASE_DIGIT_COUNT)
                digits.push_back(convertStringToInteger(findSubstring(s, i - BASE_DIGIT_COUNT + 1, i)));
        }
        fixInteger();
    }

    static SignedBigInteger getZero() {
        SignedBigInteger result;
        result.negative = false;
        result.digits.resize(1);
        result.digits.front() = 0;
        return result;
    }

    static SignedBigInteger getOne() {
        SignedBigInteger result;
        result.negative = false;
        result.digits.resize(1, 1);
        result.digits.front() = 1;
        return result;
    }

    static SignedBigInteger fromSigned32BitInteger(int number) {
        if (number == 0)
            return getZero();
        SignedBigInteger result;
        long long value;
        if (number < 0) {
            result.negative = true;
            value = -number;
        } else {
            result.negative = false;
            value = number;
        }
        for (; value; value /= BASE)
            result.digits.push_back(value % BASE);
        return result;
    }

    short getSign() const {
        if (negative)
            return -1;
        if (digits.size() > 1 || digits.back())
            return 1;
        return 0;
    }

    bool isPositive() const {
        return getSign() > 0;
    }

    bool isNegative() const {
        return getSign() < 0;
    }

    SignedBigInteger findAbsoluteValue() const {
        SignedBigInteger result;
        result.negative = false;
        result.digits = this -> digits;
        return result;
    }

    bool isZero() const {
        return getSign() == 0;
    }

    bool isNonZero() const {
        return getSign() != 0;
    }

    bool isNonNegative() const {
        return !negative;
    }

    bool isNonPositive() const {
        return negative || (digits.size() == 1 && digits.back() == 0);
    }

    static SignedBigInteger calculateMultiplication(const SignedBigInteger &a, const SignedBigInteger &b) {
        if (a.isZero() || b.isZero())
            return getZero();
        const int lengthA = a.digits.size(), lengthB = b.digits.size();
        SignedBigInteger result;
        result.negative = (a.negative != b.negative);
        result.digits.resize(lengthA + lengthB + 1);
        for (int x = 0, y; x < lengthA; ++x)
            for (y = 0; y < lengthA; ++y)
                result.digits[x + y] += a.digits[x] * b.digits[y];
        result.fixInteger();
        return result;
    }

    friend bool operator ! (const SignedBigInteger &number) {
        return number.isZero();
    }

    friend std::ostream& operator << (std::ostream& outputStream, const SignedBigInteger &number) {
        if (number.negative)
            outputStream << '-';
        outputStream << number.digits.back();
        for (int i = (int)number.digits.size() - 2; i >= 0; --i)
            outputStream << std::setfill('0') << std::setw(BASE_DIGIT_COUNT) << number.digits[i];
        return outputStream;
    }

    friend std::istream& operator >> (std::istream& inputStream, SignedBigInteger &number) {
        std::string value;

        inputStream >> value;

        number = SignedBigInteger(value);

        return inputStream;
    }

    std::string toString() const {
        std::string result, d;

        if (negative)
            result += '-';

        result += convertIntegerToString(digits.back());

        for (int i = (int)digits.size() - 2; i >= 0; --i) {
            d = convertIntegerToString(digits.at(i));
            result += std::string(BASE_DIGIT_COUNT - (int)d.size(), '0') + d;
        }

        return result;
    }

    SignedBigInteger findPower(long long e) const {
        SignedBigInteger result = getOne(), base = (*this);
        for (; e; e >>= 1, base = base * base)
            if (e & 1)
                result = result * base;
        return result;
    }

    SignedBigInteger operator - () const {
        if (this -> isZero())
            return getZero();
        SignedBigInteger result;
        result.negative = !(this -> negative);
        result.digits = this -> digits;
        return result;
    }

    bool operator ! () {
        return !(this -> isZero());
    }

    short compare(const SignedBigInteger &number) const {
        const int lengthA = (this -> digits).size(), lengthB = number.digits.size();

        if ((this -> negative) && number.negative) {
            if (lengthA < lengthB)
                return 1;

            if (lengthA > lengthB)
                return -1;

            for (int i = lengthA - 1; i >= 0; --i) {
                if ((this -> digits)[i] < (number.digits)[i])
                    return 1;
                if ((this -> digits)[i] > (number.digits)[i])
                    return -1;
            }

            return 0;
        }

        if (this -> negative)
            return -1;

        if (number.negative)
            return 1;

        if (lengthA < lengthB)
            return -1;

        if (lengthA > lengthB)
            return 1;

        for (int i = lengthB - 1; i >= 0; --i) {
            if ((this -> digits)[i] < (number.digits)[i])
                return -1;
            if ((this -> digits)[i] > (number.digits)[i])
                return 1;
        }

        return 0;
    }

    short compareByAbsoluteValues(const SignedBigInteger &number) const {
        const int lengthA = (this -> digits).size(), lengthB = number.digits.size();

        if (lengthA < lengthB)
            return -1;

        if (lengthA > lengthB)
            return 1;

        for (int i = lengthA - 1; i >= 0; --i) {
            if ((this -> digits)[i] < (number.digits)[i])
                return -1;
            if ((this -> digits)[i] > (number.digits)[i])
                return 1;
        }

        return 0;
    }

    friend SignedBigInteger operator - (const SignedBigInteger &a, const SignedBigInteger &b) {
        return a + (-b);
    }

    friend SignedBigInteger operator + (const SignedBigInteger &a, const SignedBigInteger &b) {
        SignedBigInteger result;
        if (a.negative && b.negative) {
            result.negative = true;
            result.digits = addDigits(a.digits, b.digits);
        } else if (a.negative) {
            if (a.compareByAbsoluteValues(b) <= 0) {
                result.negative = false;
                result.digits = subtractDigits(b.digits, a.digits);
            } else {
                result.negative = true;
                result.digits = subtractDigits(a.digits, b.digits);
            }
        } else if (b.negative) {
            if (b.compareByAbsoluteValues(a) <= 0) {
                result.negative = false;
                result.digits = subtractDigits(a.digits, b.digits);
            } else {
                result.negative = true;
                result.digits = subtractDigits(b.digits, a.digits);
            }
        } else {
            result.negative = false;
            result.digits = addDigits(a.digits, b.digits);
        }

        result.fixInteger();

        return result;
    }

    friend bool operator == (const SignedBigInteger &a, const SignedBigInteger &b) {
        if (a.negative != b.negative)
            return false;

        const int lengthA = a.digits.size(), lengthB = b.digits.size();

        if (lengthA != lengthB)
            return false;

        for (int i = 0; i < lengthA; ++i)
            if (a.digits[i] != b.digits[i])
                return false;

        return true;
    }

    friend bool operator != (const SignedBigInteger &a, const SignedBigInteger &b) {
        if (a.negative != b.negative)
            return true;

        const int lengthA = a.digits.size(), lengthB = b.digits.size();

        if (lengthA != lengthB)
            return true;

        for (int i = 0; i < lengthA; ++i)
            if (a.digits[i] != b.digits[i])
                return true;

        return false;
    }

    friend bool operator < (const SignedBigInteger &a, const SignedBigInteger &b) {
        return a.compare(b) < 0;
    }

    friend bool operator > (const SignedBigInteger &a, const SignedBigInteger &b) {
        return a.compare(b) > 0;
    }

    friend bool operator <= (const SignedBigInteger &a, const SignedBigInteger &b) {
        return a.compare(b) <= 0;
    }

    friend bool operator >= (const SignedBigInteger &a, const SignedBigInteger &b) {
        return a.compare(b) >= 0;
    }

    int toSigned32BitInteger() const {
        const int length = digits.size();
        int result = 0;
        for (int i = length - 1; i >= 0; --i)
            result = result * BASE + digits[i];
        if (negative)
            result = -result;
        return result;
    }

    long long toSigned64BitInteger() const {
        const int length = digits.size();
        long long result = 0;
        for (int i = length - 1; i >= 0; --i)
            result = result * BASE + digits[i];
        if (negative)
            result = -result;
        return result;
    }

    friend SignedBigInteger& operator += (SignedBigInteger &a, const SignedBigInteger &b) {
        a = a + b;
        return a;
    }

    friend SignedBigInteger& operator -= (SignedBigInteger &a, const SignedBigInteger &b) {
        a = a - b;
        return a;
    }

    friend SignedBigInteger operator * (const SignedBigInteger &a, const SignedBigInteger &b) {
        if (a.isZero() || b.isZero())
            return getZero();
        SignedBigInteger result;
        result.negative = (a.negative != b.negative);
        multiplyPolynomials(a.digits, b.digits, result.digits);
        result.fixInteger();
        return result;
    }

    friend SignedBigInteger& operator *= (SignedBigInteger &a, const SignedBigInteger &b) {
        a = a * b;
        return a;
    }

    std::string findBinaryRepresentation() const {

        if (isZero())
            return "0";

        SignedBigInteger number = this -> findAbsoluteValue();
        std::vector<SignedBigInteger> p(1, getOne());
        std::string result;
        int length = 1;

        for (; p.back() <= number;) {
            ++length;
            result += '0';
            p.push_back(p.back() << 1);
        }

        for (int i = length - 2; i >= 0; --i)
            if (number >= p[i]) {
                number -= p[i];
                result[i] = '1';
            }

        if (negative)
            result += '-';

        reverse(result.begin(), result.end());

        return result;
    }

    friend SignedBigInteger operator << (const SignedBigInteger &a, const short e) {
        SignedBigInteger result(a);

        for (auto &d : result.digits)
            d <<= e;

        result.fixInteger();
        return result;
    }

    SignedBigInteger& operator ++ () {
        (*this) += getOne();
        return *this;
    }

    SignedBigInteger operator ++ (int) {
        const SignedBigInteger result = *this;
        (*this) += getOne();
        return result;
    }

    SignedBigInteger& operator -- () {
        (*this) -= getOne();
        return *this;
    }

    SignedBigInteger operator -- (int) {
        const SignedBigInteger result = *this;
        (*this) -= getOne();
        return result;
    }
};

class DisjointSet {
private:

    mutable std::vector<int> root;

public:

    DisjointSet() {};

    DisjointSet(const int n): root(n, -1) {};

    virtual ~DisjointSet() {};

    void reload() {
        std::fill(root.begin(), root.end(), -1);
    };

    int getRoot(const int x) const {
        return root[x] < 0 ? x : (root[x] = getRoot(root[x]));
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (root[x] < root[y]) {
            root[x] += root[y];
            root[y] = x;
        } else {
            root[y] += root[x];
            root[x] = y;
        }
        return true;
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    int getTreeSize(const int x) const {
        return -root[getRoot(x)];
    }

};

template<class T, const T MOD>
class Matrix {
protected:

    static T computeAddition(T x, const T y) {
        if ((x += y) >= MOD)
            x -= MOD;
        return x;
    }

    static T computeSubtraction(T x, const T y) {
        if ((x -= y) < 0)
            x += MOD;
        return x;
    }

    static T computeMultiplication(const T x, const T y) {
        return 1LL * x * y % MOD;
    }

    static T computeInverse(T b, long long e) {
        T result = 1;

        for (e = MOD - 2; e; e >>= 1, b = computeMultiplication(b, b))
            if (e & 1)
                result = computeMultiplication(result, b);

        return result;
    }

private:

    std::vector<std::vector<T> > values;

public:

    Matrix() {};

    Matrix(const int n, const int m): values(n, std::vector<T>(m)) {};

    static Matrix<T, MOD> getSquareZeroMatrix(const int n) {
        Matrix matrix;
        matrix.values.resize(n, std::vector<T>(n));
        return matrix;
    }

    static Matrix<T, MOD> getSquareZeroMatrix(const int n, const int m) {
        Matrix matrix;
        matrix.values.resize(n, std::vector<T>(m));
        return matrix;
    }

    static Matrix<T, MOD> getIdentityMatrix(const int n) {
        Matrix matrix;
        matrix.values.resize(n, std::vector<T>(n));
        for (int i = 0; i < n; ++i)
            matrix.values[i][i] = 1;
        return matrix;
    }

    bool checkSquareMatrix() const {
        return values.empty() || values.size() == values.front().size();
    }

    Matrix(const Matrix &matrix) {
        this -> values = matrix.values;
    };

    Matrix& operator = (const Matrix &matrix) {
        this -> values = matrix.values;
        return *this;
    }

    template<class A, class B>
    void getShape(A &n, B &m) const {
        if (values.empty()) {
            n = m = 0;
            return;
        }
        n = values.size();
        m = values.front().size();
    }

    std::pair<int, int> getShape() const {
        if (values.empty())
            return std::make_pair(0, 0);
        return std::make_pair(values.size(), values.front().size());
    }

    std::vector<T>& operator [] (const int r) {
        return values[r];
    }

    const std::vector<T>& operator [] (const int r) const {
        return values[r];
    }

    friend Matrix operator * (const Matrix &a, const Matrix &b) {
        const auto [n, m] = a.getShape();
        const auto [p, k] = b.getShape();

        assert(m == p);

        Matrix result(n, k);
        for (int i = 0, j, z; i < n; ++i)
            for (j = 0; j < p; ++j)
                for (z = 0; z < m; ++z)
                    result[i][j] = computeAddition(result[i][j], computeMultiplication(a[i][z], b[z][j]));

        return result;
    }

    friend Matrix operator + (Matrix a, const Matrix &b) {
        const auto [n, m] = a.getShape();

        for (int x = 0, y; x < n; ++x)
            for (y = 0; y < m; ++y)
                a[x][y] = computeAddition(a[x][y], b[x][y]);

        return a;
    }

    friend Matrix operator - (Matrix a, const Matrix &b) {
        const auto [n, m] = a.getShape();

        for (int x = 0, y; x < n; ++x)
            for (y = 0; y < m; ++y)
                a[x][y] = computeSubtraction(a[x][y], b[x][y]);

        return a;
    }

    friend Matrix& operator *= (Matrix &a, const Matrix &b) {
        a = a * b;
        return a;
    }

    int getNumberOfRows() const {
        return values.size();
    }

    int getNumberOfColumns() const {
        if (values.empty())
            return 0;
        return values.front().size();
    }

    static Matrix findPower(Matrix base, long long exponential) {
        const int n = base.getNumberOfRows();
        Matrix result = getIdentityMatrix(n);
        for (; exponential; exponential >>= 1, base *= base)
            if (exponential & 1)
                result *= base;
        return result;
    }

    bool checkEmpty() const {
        return values.empty();
    }

    bool checkNonEmpty() const {
        return !values.empty();
    }

    void swapRows(const int u, const int v) {
        for (int y = getNumberOfColumns() - 1; y >= 0; --y)
            swap(values[u][y], values[v][y]);
    }

    friend std::ostream& operator << (std::ostream &outputStream, const Matrix &m) {
        if (m.values.empty())
            return outputStream << "[]";

        outputStream << "[\n";

        for (const auto &row : m.values) {
            outputStream << '[';

            if (!row.empty()) {
                const int length = row.size();
                outputStream << std::setw(20) << row.front();
                for (int i = 1; i < length; ++i)
                    outputStream << ',' << std::setw(20) << row[i];
            }

            outputStream << "]\n";
        }

        return outputStream << ']';
    }

};

using namespace std;

constexpr int MAX_N = 1003, MAX_M = 1003, MAX_2N = 2003, MAX_2M = 2003, MAX_4MN = 4E6 + 6;
const pair<int, int> BASE(2999, 2777), MOD(1E9 + 9999, 1E9 + 123);

pair<int, int> computeMultiplication(const pair<long long, long long> &x,
                                     const pair<long long, long long> &y) {
    return make_pair(
                     x.first * y.first % MOD.first,
                     x.second * y.second % MOD.second);
}

pair<int, int>& setMultiplied(pair<int, int> &x,
                              const pair<long long, long long> &y) {
    x.first = x.first * y.first % MOD.first;
    x.second = x.second * y.second % MOD.second;
    return x;
}

pair<int, int>& setAdded(pair<int, int> &x,
                         const pair<int, int> &y) {
    if ((x.first += y.first) >= MOD.first)
        x.first -= MOD.first;
    if ((x.second += y.second) >= MOD.second)
        x.second -= MOD.second;
    return x;
}

pair<int, int>& setSubtracted(pair<int, int> &x,
                         const pair<int, int> &y) {
    if ((x.first -= y.first) < 0)
        x.first += MOD.first;
    if ((x.second -= y.second) < 0)
        x.second += MOD.second;
    return x;
}

pair<int, int> computeAddition(pair<int, int> x,
                               const pair<int, int> &y) {
    if ((x.first += y.first) >= MOD.first)
        x.first -= MOD.first;
    if ((x.second += y.second) >= MOD.second)
        x.second -= MOD.second;
    return x;
}

pair<int, int> computeSubtraction(pair<int, int> x,
                                  const pair<int, int> &y) {
    if ((x.first -= y.first) < 0)
        x.first += MOD.first;
    if ((x.second -= y.second) < 0)
        x.second += MOD.second;
    return x;
}

signed N, M;
int n = 4E6, m;
string image[MAX_2N];
pair<signed, signed> result(1, 1);
pair<int, int> row[MAX_2N][MAX_2M], power[MAX_4MN], h[MAX_2M][MAX_2N];

pair<int, int> query(const pair<int, int> h[], const int l, const int r) {
    return computeSubtraction(h[r], computeMultiplication(h[l - 1], power[r - l + 1]));
}

pair<int, int> query(const int y, const int l, const int r) {
    return computeSubtraction(h[y][r], computeMultiplication(h[y][l - 1], power[(l - 1) * m]));
}

bool checkSmaller(const int x1, const int y1, const int x2, const int y2) {
    int low = 0, high = m + 1, middle;
    for (; low + 1 < high;) {
        middle = low + high >> 1;
        if (query(row[x1], y1, y1 + middle - 1) == query(row[x2], y2, y2 + middle - 1))
            low = middle;
        else
            high = middle;
    }
    return low < m && image[x1 - 1][y1 - 1 + low] < image[x2 - 1][y2 - 1 + low];
}

bool inspectSmaller(const int x1, const int y1, const int x2, const int y2) {
    int low = 0, high = n + 1, middle;
    for (; low + 1 < high;) {
        middle = low + high >> 1;
        if (query(y1, x1, x1 + middle - 1) == query(y2, x2, x2 + middle - 1))
            low = middle;
        else
            high = middle;
    }
    return low < n && checkSmaller(x1 + low, y1, x2 + low, y2);
}

pair<int, int> getDuplicatedNumbers(const int x) {
    return make_pair(x, x);
}

signed main() {

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    power[0] = make_pair(1, 1);

    for (int i = 1; i <= n; ++i)
        power[i] = computeMultiplication(power[i - 1], BASE);

    cin >> n >> m;

    N = n << 1;
    M = m << 1;

    for (int x = 0, y; x < n; ++x) {
        cin >> image[x];
        image[x] += image[x];
        image[x + n] = image[x];
        for (y = 1; y <= M; ++y)
            row[x + 1][y] = row[x + 1 + n][y] = computeAddition(getDuplicatedNumbers(image[x][y - 1]), computeMultiplication(row[x + 1][y - 1], BASE));
    }

    for (int x = 1, y; x <= N; ++x)
        for (y = 1; y <= m; ++y)
            h[y][x] = computeAddition(query(row[x], y, y + m - 1), computeMultiplication(h[y][x - 1], power[m]));

    for (int x = 1, y; x <= n; ++x)
        for (y = 1; y <= m; ++y)
            if (inspectSmaller(x, y, result.first, result.second))
                result = make_pair(x, y);

    for (int x = 0, y; x < n; ++x) {
        for (y = 0; y < m; ++y)
            cout << image[result.first + x - 1][result.second + y - 1];
        cout << '\n';
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In static member function 'static int SignedBigInteger::getReversedBits(int, int)':
Main.cpp:96:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   96 |                 result |= 1 << n - 1 - i;
      |                                ~~~~~~^~~
Main.cpp: In function 'bool checkSmaller(int, int, int, int)':
Main.cpp:939:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  939 |         middle = low + high >> 1;
      |                  ~~~~^~~~~~
Main.cpp: In function 'bool inspectSmaller(int, int, int, int)':
Main.cpp:951:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  951 |         middle = low + high >> 1;
      |                  ~~~~^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60