oj.uz

Submission #1011852

# Submission time Handle Problem Language Result Execution time Memory
1011852 2024-07-01T09:47:49 Z MuhammadSaram Sateliti (COCI20_satellti) C++17
10 / 110
 62 ms 16016 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 2001;
const int p1 = 727, q1 = 311, mod1 = 1e9 + 9;
const int p2 = 919, q2 = 673, mod2 = 1e9 + 7;

int pre1[M][M], pw1[M], ivp1[M], qw1[M], ivq1[M];
int pre2[M][M], pw2[M], ivp2[M], qw2[M], ivq2[M];
char a[M][M];

int power(int a, int b, int mod) {
    int ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int hsh1(int x, int y, int cnt, int m) {
    int ans = 0;
    if (cnt / m)
        ans = pre1[x + cnt / m - 1][y + m - 1] - pre1[x + cnt / m - 1][y - 1] - pre1[x - 1][y + m - 1] + pre1[x - 1][y - 1];
    if (cnt % m)
        ans += pre1[x + cnt / m][y + cnt % m - 1] - pre1[x + cnt / m][y - 1] - pre1[x - 1][y + cnt % m - 1] + pre1[x - 1][y - 1];
    ans += mod1 * 4, ans %= mod1;
    ans = ans * ivp1[x] % mod1 * ivq1[y] % mod1;
    return ans;
}

int hsh2(int x, int y, int cnt, int m) {
    int ans = 0;
    if (cnt / m)
        ans = pre2[x + cnt / m - 1][y + m - 1] - pre2[x + cnt / m - 1][y - 1] - pre2[x - 1][y + m - 1] + pre2[x - 1][y - 1];
    if (cnt % m)
        ans += pre2[x + cnt / m][y + cnt % m - 1] - pre2[x + cnt / m][y - 1] - pre2[x - 1][y + cnt % m - 1] + pre2[x - 1][y - 1];
    ans += mod2 * 4, ans %= mod2;
    ans = ans * ivp2[x] % mod2 * ivq2[y] % mod2;
    return ans;
}

bool comp(int x1, int y1, int x2, int y2, int n, int m) {
    int s = 0, e = n * m + 1;
    while (s + 1 < e) {
        int mid = (s + e) / 2;
        if (hsh1(x1, y1, mid, m) == hsh1(x2, y2, mid, m) && hsh2(x1, y1, mid, m) == hsh2(x2, y2, mid, m))
            s = mid;
        else
            e = mid;
    }
    if (s == n * m)
        return 0;
    return (a[x1 + s / m][y1 + s % m] == '*');
}

signed main() {
    int n, m;
    cin >> n >> m;
    n *= 2, m *= 2;
    for (int i = 1; i <= n / 2; i++)
        for (int j = 1; j <= m / 2; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n / 2; i++)
        for (int j = m / 2 + 1; j <= m; j++)
            a[i][j] = a[i][j - m / 2];
    for (int i = n / 2 + 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = a[i - n / 2][j];

    pw1[0] = qw1[0] = 1;
    pw2[0] = qw2[0] = 1;
    for (int i = 1; i < M; i++) {
        pw1[i] = pw1[i - 1] * p1 % mod1;
        qw1[i] = qw1[i - 1] * q1 % mod1;
        pw2[i] = pw2[i - 1] * p2 % mod2;
        qw2[i] = qw2[i - 1] * q2 % mod2;
    }
    ivp1[M - 1] = power(pw1[M - 1], mod1 - 2, mod1);
    ivq1[M - 1] = power(qw1[M - 1], mod1 - 2, mod1);
    ivp2[M - 1] = power(pw2[M - 1], mod2 - 2, mod2);
    ivq2[M - 1] = power(qw2[M - 1], mod2 - 2, mod2);
    for (int i = M - 2; i >= 0; i--) {
        ivp1[i] = ivp1[i + 1] * p1 % mod1;
        ivq1[i] = ivq1[i + 1] * q1 % mod1;
        ivp2[i] = ivp2[i + 1] * p2 % mod2;
        ivq2[i] = ivq2[i + 1] * q2 % mod2;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            pre1[i][j] = pre1[i - 1][j] + pre1[i][j - 1] - pre1[i - 1][j - 1];
            pre1[i][j] += a[i][j] * pw1[i - 1] % mod1 * qw1[j - 1] % mod1;
            pre1[i][j] %= mod1;
            pre2[i][j] = pre2[i - 1][j] + pre2[i][j - 1] - pre2[i - 1][j - 1];
            pre2[i][j] += a[i][j] * pw2[i - 1] % mod2 * qw2[j - 1] % mod2;
            pre2[i][j] %= mod2;
        }

    int idx = 1, idy = 1;
    for (int i = 1; i + n / 2 - 1 <= n; i++)
        for (int j = 1; j + m / 2 - 1 <= m; j++) {
            if (comp(i, j, idx, idy, n / 2, m / 2))
                idx = i, idy = j;
        }
    for (int i = idx; i < idx + n / 2; i++) {
        for (int j = idy; j < idy + m / 2; j++)
            cout << a[i][j];
        cout << endl;
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 7164 KB Output is correct
8 Correct 38 ms 15824 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 36 ms 15844 KB Output is correct
12 Incorrect 62 ms 16016 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 7164 KB Output is correct
8 Correct 38 ms 15824 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 36 ms 15844 KB Output is correct
12 Incorrect 62 ms 16016 KB Output isn't correct
13 Halted 0 ms 0 KB -