제출 #377592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377592		NONAME	Sateliti (COCI20_satellti)	C++17	110 / 110	759 ms	49516 KiB

Main

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int man = (int)(1e3 + 10);
const int base = (int)(1e9 + 7);

int n, m;
int pw[man + man][man + man];
int a[man + man][man + man], pf[man + man][man + man];

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

int mul(int x, int y) {
    return (x * 1LL * y) % base;
}

int bp(int x, int y) {
    int ret = 1;
    while (y) {
        if (y & 1) {
            ret = mul(ret, x);
        }
        x = mul(x, x);
        y >>= 1;
    }
    return ret;
}

int get(int x, int y, int X, int Y, int lx, int ly) {
    int hsh = sum(pf[X][Y], -pf[x - 1][Y]);
    hsh = sum(hsh, -pf[X][y - 1]);
    hsh = sum(hsh, pf[x - 1][y - 1]);
    hsh = mul(hsh, pw[lx][ly]);
    // cerr << hsh << "\n";
    return hsh;
}

void check(int x, int y, int& pi, int& pj) {
    get(x, y, x, y + 1, pi - 1, pj - 1);
    get(pi, pj, pi, pj + 1, x - 1, y - 1);

    int l = 1, r = n;
    while (l < r) {
        int md = (l + r) >> 1;
        if (get(x, y, x + md - 1, y + m - 1, pi - 1, pj - 1) != get(pi, pj, pi + md - 1, pj + m - 1, x - 1, y - 1)) {
            r = md;
        } else {
            l = md + 1;
        }
    }

    int len = l;
    // cerr << len << "\n";

    l = 1; r = m;

    // cerr << get(x, x, y, y) << " " << get(pi, pi, pj, pj) << "\n";

    while (l < r) {
        int md = (l + r) >> 1;
        // cerr << md << " " << get(x + len - 1, x + len - 1, y, y + md - 1) << " " << get(pi + len - 1, pi + len - 1, pj, pj + md - 1) << "\n";
        if (get(x + len - 1, y, x + len - 1, y + md - 1, pi + len - 2, pj - 1) != get(pi + len - 1, pj, pi + len - 1, pj + md - 1, x + len - 2, y - 1)) {
            r = md;
        } else {
            l = md + 1;
        }
    }
    // cerr << l << "\n";

    // cerr << x << " " << y << " " << len << " " << l << "\n";
    // cerr << a[x + len - 1][y + l - 1] << " " << a[pi + len - 1][pj + l - 1] << "\n";
    if (a[x + len - 1][y + l - 1] < a[pi + len - 1][pj + l - 1]) {
        pi = x;
        pj = y;
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            if (c == '*') {
                a[i][j] = 0;
            } else {
                a[i][j] = 1;
            }
            a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
        }
    }

    // for (int i = 1; i <= (n + n); ++i, cerr << "\n") {
    //     for (int j = 1; j <= (m + m); ++j) {
    //         cerr << a[i][j];
    //     }
    // }

    pw[0][0] = 1;
    for (int i = 0; i < (n + n); ++i) {
        for (int j = 0; j < (m + m); ++j) {
            if ((i == 0) && (j == 0)) {
                continue;
            }
            if (i == 0) {
                pw[i][j] = mul(pw[i][j - 1], 5);
            } else {
                pw[i][j] = mul(pw[i - 1][j], 7);
            }
        }
    }

    for (int i = 1; i <= (n + n); ++i) {
        for (int j = 1; j <= (m + m); ++j) {
            int hsh = mul(a[i][j] + 1, pw[i - 1][j - 1]);
            pf[i][j] = sum(sum(pf[i][j - 1], sum(pf[i - 1][j], -pf[i - 1][j - 1])), hsh);
        }
    }

    int pi = 1, pj = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // if ((i == 2) && (j == 2)) {
            //     cerr << pi << " " << pj << "\n";
            // }
            check(i, j, pi, pj);
        }
    }

    // pi = 1; pj = 2;
    // cerr << pi << " " << pj << "\n";
    // check(2, 2, pi, pj);


    for (int i = pi; i <= (pi + n - 1); ++i, cout << "\n") {
        for (int j = pj; j <= (pj + m - 1); ++j) {
            cout << (a[i][j] ? '.' : '*');
        }
    }

    return 0;
}

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