Submission #1137887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137887		eysbutno	Sateliti (COCI20_satellti)	C++20	110 / 110	419 ms	64220 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = array<int, 2>;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

constexpr int M = 1e9 + 9;
constexpr int B = 9973;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector grid(2 * n, vector<int>(2 * m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            grid[i][j] = c;
            grid[i + n][j] = c;
            grid[i][j + m] = c;
            grid[i + n][j + m] = c;
        }
    }

    vector<ll> pows(max(n, m) + 1);
    pows[0] = 1;
    for (int i = 1; i < pows.size(); i++) {
        pows[i] = (pows[i - 1] * B) % M;
    }

    vector row(m, vector<ll>(2 * n));
    vector col(2 * n, vector<ll>(2 * m));

    const auto get_hash = [&](const vector<ll> &arr, int l, int r) -> ll {
        ll raw = arr[r] - pows[r - l + 1] * (l <= 0 ? 0 : arr[l - 1]);
        return (raw % M + M) % M;
    };

    for (int i = 0; i < 2 * n; i++) {
        ll cur = 0;
        for (int j = 0; j < 2 * m; j++) {
            cur = (cur * B + grid[i][j]) % M;
            col[i][j] = cur;
        }

        for (int j = 0; j < m; j++) {
            ll prv = (i > 0) ? row[j][i - 1] : 0;
            row[j][i] = (prv * B + get_hash(col[i], j, j + m - 1)) % M;
        }
    }

    int best_r = 0, best_c = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int lo = 0, hi = n - 1;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                bool mismatch = get_hash(row[best_c], best_r, best_r + mid)
                             != get_hash(row[j], i, i + mid);
                (mismatch) ? hi = mid : lo = mid + 1;
            }

            if (get_hash(row[best_c], best_r, best_r + n - 1) == get_hash(row[j], i, i + n - 1)) {
                continue;
            }

            int off = lo;
			
            lo = 0, hi = m - 1;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                bool mismatch = get_hash(col[best_r + off], best_c, best_c + mid)
                             != get_hash(col[i + off], j, j + mid);
                (mismatch) ? hi = mid : lo = mid + 1;
            }

            if (grid[i + off][j + lo] < grid[best_r + off][best_c + lo]) {
                best_r = i, best_c = j;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << char(grid[best_r + i][best_c + j]);
        }
        cout << "\n";
    }

    // cout << best_r + 1 << " " << best_c + 1 << "\n";

    /*
    for (int i = 0; i < n; i++) {
        cout << get_hash(row[1], 0, i) << " " << get_hash(row[0], 1, 1 + i) << "\n";
    }
    */

    /*
    cout << get_hash(col[0], 1, 4) << " " << get_hash(col[1], 3, 6) 
         << " " << get_hash(col[2], 0, 3) << "\n";

    const auto print = [&](int row, int l, int r) -> void {
        for (int i = l; i <= r; i++) {
            cout << char(grid[row][i]);
        }
        cout << "\n";
    };

    print(0, 1, 4);
    print(1, 3, 6);
    print(2, 0, 3);
    */
}

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