제출 #1262374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262374		askeww	Sateliti (COCI20_satellti)	C++20	110 / 110	586 ms	64036 KiB

Main

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

#define M(X) (X % P + P) % P

template<typename T>
using V = vector<T>;
using ll = long long;

const ll P = 1000000007LL, A = 10007LL, B = 10009LL;

int n, m, ansl, ansr, lo, hi, mi, bi;
char c;
V<V<ll>> a, h;
V<ll> pa, pb, pia, pib;
ll inv;

ll exp(ll b, ll e) {
    ll res = 1;
    while (e != 0) {
        if (e & 1) res = (res * b) % P;
        b = (b * b) % P;
        e >>= 1;
    }
    return res;
}

ll ch(ll a, ll b, ll c, ll d) {
    return M(M(M(h[c][d] - (a - 1 >= 0 ? h[a - 1][d] : 0) - (b - 1 >= 0 ? h[c][b - 1] : 0) + (a - 1 >= 0 && b - 1 >= 0 ? h[a - 1][b - 1] : 0)) * pia[a]) * pib[b]);
}

int main() {
    cin >> n >> m;

    inv = exp(A, P - 2);
    pa = pia = V<ll>(2 * n);
    pa[0] = pia[0] = 1;
    for (int i = 1; i < 2 * n; i++) {
        pa[i] = M(pa[i - 1] * A);
        pia[i] = M(pia[i - 1] * inv);
    }

    inv = exp(B, P - 2);
    pb = pib = V<ll>(2 * m);
    pb[0] = pib[0] = 1;
    for (int i = 1; i < 2 * m; i++) {
        pb[i] = M(pb[i - 1] * B);
        pib[i] = M(pib[i - 1] * inv);
    }

    a = V<V<ll>>(2 * n, V<ll>(2 * m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c;
            if (c == '*') a[i][j] = 1;
            if (c == '.') a[i][j] = 2;
            a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
        }
    }

    h = V<V<ll>>(2 * n, V<ll>(2 * m));
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * m; j++) {
            h[i][j] = M((i > 0 ? h[i - 1][j] : 0)
                    + (j > 0 ? h[i][j - 1] : 0)
                    - M((i > 0 && j > 0 ? h[i - 1][j - 1] : 0)
                    + M(M(a[i][j] * pa[i]) * pb[j])));
        }
    }
    
    ansl = ansr = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            lo = 0, hi = n;
            while (lo < hi) {
                mi = (lo + hi) / 2;

                if (ch(ansl, ansr, ansl + mi, ansr + m - 1) == ch(i, j, i + mi, j + m - 1)) {
                    lo = mi + 1;
                } else {
                    hi = mi;
                }
            }
            bi = hi;

            if (bi == n) continue;

            lo = 0, hi = m - 1;
            while (lo < hi) {
                mi = (lo + hi) / 2;

                if (ch(ansl, ansr, ansl + bi, ansr + mi) == ch(i, j, i + bi, j + mi)) {
                    lo = mi + 1;
                } else {
                    hi = mi;
                }
            }

            if (a[i + bi][j + hi] < a[ansl + bi][ansr + hi]) {
                ansl = i;
                ansr = j;
            }
        }
    }
    
    for (int ki = 0; ki < n; ki++) {
        for (int kj = 0; kj < m; kj++) {
            cout << (a[ansl + ki][ansr + kj] == 1 ? "*" : ".");
        }
        cout << '\n';
    }
    cout << '\n';
}

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