oj.uz

Submission #514093

# Submission time Handle Problem Language Result Execution time Memory
514093 2022-01-18T03:27:44 Z KoD Sateliti (COCI20_satellti) C++17
110 / 110
 1607 ms 37712 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 117 ms 3416 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 106 ms 3524 KB Output is correct
12 Correct 108 ms 3520 KB Output is correct
13 Correct 110 ms 3616 KB Output is correct
14 Correct 116 ms 3616 KB Output is correct
15 Correct 116 ms 3620 KB Output is correct
16 Correct 127 ms 3612 KB Output is correct
17 Correct 129 ms 3616 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 117 ms 3416 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 106 ms 3524 KB Output is correct
12 Correct 108 ms 3520 KB Output is correct
13 Correct 110 ms 3616 KB Output is correct
14 Correct 116 ms 3616 KB Output is correct
15 Correct 116 ms 3620 KB Output is correct
16 Correct 127 ms 3612 KB Output is correct
17 Correct 129 ms 3616 KB Output is correct
18 Correct 1438 ms 37496 KB Output is correct
19 Correct 11 ms 832 KB Output is correct
20 Correct 21 ms 972 KB Output is correct
21 Correct 1412 ms 37596 KB Output is correct
22 Correct 1523 ms 37596 KB Output is correct
23 Correct 1432 ms 37712 KB Output is correct
24 Correct 1513 ms 37596 KB Output is correct
25 Correct 1433 ms 37600 KB Output is correct
26 Correct 1526 ms 37700 KB Output is correct
27 Correct 1607 ms 37520 KB Output is correct