oj.uz

Submission #514088

# Submission time Handle Problem Language Result Execution time Memory
514088 2022-01-18T03:24:05 Z KoD Sateliti (COCI20_satellti) C++17
10 / 110
 3000 ms 10248 KB 
#include <bits/stdc++.h>

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

using u64 = std::uint64_t;
using u128 = std::uint64_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;
        }
    }
    for (int i = 0; i <= 2 * N; ++i) {
        for (int j = 0; j <= 2 * M; ++j) {
            std::cerr << hash[i][j].x << " \n"[j == 2 * M];
        }
    }
    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);
        for (int x = i; x < k; ++x) {
            for (int y = j; y < l; ++y) {
                ret += Fp(grid[x][y]) * pow<Bx>(x - i) * pow<By>(y - j);
            }
        }
        return ret;
    };
    std::cerr << rect(0, 0, N, M).x << '\n';
    std::cerr << rect(0, M, N, 2 * M).x << '\n';
    std::cerr << rect(N, 0, 2 * N, M).x << '\n';
    std::cerr << rect(N, M, 2 * N, 2 * M).x << '\n';
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 632 KB Output is correct
2 Correct 213 ms 564 KB Output is correct
3 Correct 229 ms 564 KB Output is correct
4 Correct 142 ms 580 KB Output is correct
5 Correct 219 ms 564 KB Output is correct
6 Correct 268 ms 572 KB Output is correct
7 Correct 127 ms 568 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 632 KB Output is correct
2 Correct 213 ms 564 KB Output is correct
3 Correct 229 ms 564 KB Output is correct
4 Correct 142 ms 580 KB Output is correct
5 Correct 219 ms 564 KB Output is correct
6 Correct 268 ms 572 KB Output is correct
7 Correct 127 ms 568 KB Output is correct
8 Execution timed out 3053 ms 10248 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 632 KB Output is correct
2 Correct 213 ms 564 KB Output is correct
3 Correct 229 ms 564 KB Output is correct
4 Correct 142 ms 580 KB Output is correct
5 Correct 219 ms 564 KB Output is correct
6 Correct 268 ms 572 KB Output is correct
7 Correct 127 ms 568 KB Output is correct
8 Execution timed out 3053 ms 10248 KB Time limit exceeded
9 Halted 0 ms 0 KB -