제출 #514093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
514093		KoD	Sateliti (COCI20_satellti)	C++17	110 / 110	1607 ms	37712 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using u64 = std::uint64_t;
using u128 = __uint128_t;

constexpr u64 MOD = ((u64)1 << 61) - 1;

struct Fp {
    u64 x;
    Fp(const u64 x = 0) : x(x) {}
    Fp& operator+=(const Fp& t) {
        if ((x += t.x) >= MOD) x -= MOD;
        return *this;
    }
    Fp& operator-=(const Fp& t) {
        if (x < t.x) x += MOD;
        x -= t.x;
        return *this;
    }
    Fp& operator*=(const Fp& t) {
        const auto y = (u128)x * t.x;
        x = (y >> 61) + (y & MOD);
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Fp operator+(const Fp& t) const { 
        return Fp(*this) += t; 
    }
    Fp operator-(const Fp& t) const { 
        return Fp(*this) -= t; 
    }
    Fp operator*(const Fp& t) const { 
        return Fp(*this) *= t; 
    }
    bool operator==(const Fp& t) const {
        return x == t.x;
    }
};

constexpr u64 Bx = 10000;
constexpr u64 By = 100;

template <u64 B> Fp pow(const int n) {
    static vector<Fp> vec = {1};
    while ((int)vec.size() <= n) {
        vec.push_back(vec.back() * B);
    }
    return vec[n];
}

template <class F> int binary_search(int ok, int ng, const F& f) {
    while (std::abs(ok - ng) > 1) {
        const int md = (ok + ng) / 2;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector grid(2 * N, vector<char>(2 * M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            char c;
            std::cin >> c;
            grid[i][j] = grid[i + N][j] = grid[i][j + M] = grid[i + N][j + M] = c;
        }
    }
    vector hash(2 * N + 1, vector<Fp>(2 * M + 1));
    for (int i = 0; i < 2 * N; ++i) {
        for (int j = 0; j < 2 * M; ++j) {
            hash[i + 1][j + 1] += grid[i][j];
            hash[i + 1][j + 1] += hash[i][j + 1] * Bx;
            hash[i + 1][j + 1] += hash[i + 1][j] * By;
            hash[i + 1][j + 1] -= hash[i][j] * Bx * By;
        }
    }
    const auto rect = [&](const int i, const int j, const int k, const int l) {
        Fp ret = 0;
        ret += hash[k][l];
        ret -= hash[i][l] * pow<Bx>(k - i);
        ret -= hash[k][j] * pow<By>(l - j);
        ret += hash[i][j] * pow<Bx>(k - i) * pow<By>(l - j);
        return ret;
    };
    int x = 0, y = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (rect(x, y, x + N, y + M) == rect(i, j, i + N, j + M)) {
                continue;
            }
            const int h = binary_search(0, N, [&](const int thres) {
                return rect(x, y, x + thres, y + M) == rect(i, j, i + thres, j + M);
            });
            const int w = binary_search(0, M, [&](const int thres) {
                return rect(x + h, y, x + h + 1, y + thres) == rect(i + h, j, i + h + 1, j + thres);
            });
            if (grid[x + h][y + w] > grid[i + h][j + w]) {
                x = i, y = j;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            std::cout << grid[x + i][y + j];
        }
        std::cout << '\n';
    }
    return 0;
}

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