제출 #377403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377403		VEGAnn	Sateliti (COCI20_satellti)	C++14	110 / 110	518 ms	124416 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int oo = 2e9;
const int N = 2010;
const int M = 11;
const int PW = 10;
const int HPW = 233;
const int md = int(1e9) + 7;
bool mat[N][N];
int n, m, hsh[N][N];
int sms[N][N][PW], prec[N * N];

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int sub(int x, int y){
    x -= y;
    if (x < 0)
        x += md;
    return x;
}

int mult(int x, int y) { return (1ll * x * y) % md; }

int get_hsh(int id, int lf, int rt){
    return sub(hsh[id][lf], mult(hsh[id][rt + 1], prec[rt - lf + 1]));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    prec[0] = 1;

    for (int i = 1; i < N * N; i++)
        prec[i] = mult(prec[i - 1], HPW);

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        char c; cin >> c;

        mat[i][j] = bool(c == '*');
    }

    for (int i = 0; i < n + n; i++)
    for (int j = 0; j < m + m; j++)
        mat[i][j] = mat[(i % n)][(j % m)];

    for (int i = 0; i < n + n; i++){
        hsh[i][m + m] = 0;

        for (int j = m + m - 1; j >= 0; j--)
            hsh[i][j] = sum(mult(hsh[i][j + 1], HPW), mat[i][j] + 1);

        for (int j = 0; j < m; j++)
            sms[i][j][0] = get_hsh(i, j, j + m - 1);
    }

    for (int po = 1; po < PW; po++)
    for (int i = 0; ; i++){
        if (i + (1 << po) > n + n) break;

        int NOW = prec[m * (1 << (po - 1))];

        for (int j = 0; j < m; j++)
            sms[i][j][po] = sum(sms[i][j][po - 1], mult(NOW, sms[i + (1 << (po - 1))][j][po - 1]));
    }

    int bx = 0, by = 0;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        if (i == 0 && j == 0) continue;

        int len = 0;

        for (int po = PW - 1; po >= 0; po--){
            if (len + (1 << po) > n) continue;

            if (sms[i + len][j][po] != sms[bx + len][by][po]) continue;

            len += (1 << po);
        }

        if (len == n) continue;

        int l = 0, r = m - 1;

        while (l < r){
            int md = (l + r) >> 1;

            if (get_hsh(i + len,  j,  j + md) !=
                get_hsh(bx + len, by, by + md))
                r = md;
            else l = md + 1;
        }

        assert(mat[i + len][j + l] != mat[bx + len][by + l]);

        if (mat[i + len][j + l] > mat[bx + len][by + l]){
            bx = i;
            by = j;
        }
    }

    for (int i = bx; i < bx + n; i++){
        for (int j = by; j < by + m; j++)
            cout << (mat[i][j] ? '*' : '.');
        cout << '\n';
    }

    return 0;
}

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