oj.uz

Submission #1103093

# Submission time Handle Problem Language Result Execution time Memory
1103093 2024-10-20T00:41:14 Z orcslop Sateliti (COCI20_satellti) C++17
110 / 110
 587 ms 37736 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define f first
#define s second

const int N = 2e3 + 7, base1 = 311, base2 = 10007, MOD = 1e9 + 7;

int n, m;
ll pw[N], pw2[N], h[N][N];
char a[N][N];

void prepare() {
    pw[0] = pw2[0] = 1;
    for (int i = 1; i <= 2 * n; i++) pw[i] = pw[i - 1] * base1 % MOD;
    for (int i = 1; i <= 2 * m; i++) pw2[i] = pw2[i - 1] * base2 % MOD;
    for (int i = 1; i <= 2 * n; i++){
        for (int j = 1; j <= 2 * m; j++) {
            h[i][j] = (h[i - 1][j] * base1 % MOD + h[i][j - 1] * base2 % MOD) % MOD;
            (h[i][j] -= h[i - 1][j - 1] * base1 * base2 % MOD + a[i][j] - 'a' + 1) %= MOD;
        }
    }
}

int get(int a, int b, int x, int y) {
    ll ret = (h[x][y] - h[a - 1][y] * pw[x - a + 1] % MOD - h[x][b - 1] * pw2[y - b + 1] + 1ll * MOD * MOD) % MOD;
    (ret += h[a - 1][b - 1] * pw[x - a + 1] % MOD * pw2[y - b + 1] % MOD + 1ll * MOD * MOD) %= MOD;
    return ret;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            a[i][j + m] = a[i][j];
            a[i + n][j] = a[i][j];
            a[i + n][j + m] = a[i][j];
        }
    } 
    prepare();

    pair<int, int> pos = {1, 1};
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int l = 1, r = n, ans = -1, ans1 = -1;
            while (l <= r) {
                int mid = l + r >> 1;
                if (get(i, j, i + mid - 1, j + m - 1) == get(pos.f, pos.s, pos.f + mid - 1, pos.s + m - 1)) l = mid + 1;
                else ans = mid, r = mid - 1;
            }
            if (ans == -1) continue;

            l = 1, r = m;
            while (l <= r) {
                int mid = l + r >> 1;
                if (get(i, j, i + ans - 1, j + mid - 1) == get(pos.f, pos.s, pos.f + ans - 1, pos.s + mid - 1)) l = mid + 1;
                else ans1 = mid, r = mid - 1;
            }

            if (ans1 == -1) continue;
            if (a[i + ans - 1][j + ans1 - 1] < a[pos.f + ans - 1][pos.s + ans1 - 1]) pos = {i, j};
        }

    for (int i = pos.f; i < pos.f + n; i++) {
        for (int j = pos.s; j < pos.s + m; j++)
            cout << a[i][j];
        cout << '\n';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:48:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |                 int mid = l + r >> 1;
      |                           ~~^~~
Main.cpp:56:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |                 int mid = l + r >> 1;
      |                           ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 2 ms 940 KB Output is correct
5 Correct 2 ms 3152 KB Output is correct
6 Correct 3 ms 3152 KB Output is correct
7 Correct 2 ms 3368 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 2 ms 940 KB Output is correct
5 Correct 2 ms 3152 KB Output is correct
6 Correct 3 ms 3152 KB Output is correct
7 Correct 2 ms 3368 KB Output is correct
8 Correct 42 ms 8528 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 4864 KB Output is correct
11 Correct 42 ms 8736 KB Output is correct
12 Correct 46 ms 8952 KB Output is correct
13 Correct 47 ms 9004 KB Output is correct
14 Correct 47 ms 8920 KB Output is correct
15 Correct 43 ms 8788 KB Output is correct
16 Correct 46 ms 8920 KB Output is correct
17 Correct 51 ms 8908 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 2 ms 940 KB Output is correct
5 Correct 2 ms 3152 KB Output is correct
6 Correct 3 ms 3152 KB Output is correct
7 Correct 2 ms 3368 KB Output is correct
8 Correct 42 ms 8528 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 4864 KB Output is correct
11 Correct 42 ms 8736 KB Output is correct
12 Correct 46 ms 8952 KB Output is correct
13 Correct 47 ms 9004 KB Output is correct
14 Correct 47 ms 8920 KB Output is correct
15 Correct 43 ms 8788 KB Output is correct
16 Correct 46 ms 8920 KB Output is correct
17 Correct 51 ms 8908 KB Output is correct
18 Correct 540 ms 37552 KB Output is correct
19 Correct 10 ms 12884 KB Output is correct
20 Correct 8 ms 1108 KB Output is correct
21 Correct 499 ms 37620 KB Output is correct
22 Correct 587 ms 37708 KB Output is correct
23 Correct 484 ms 37708 KB Output is correct
24 Correct 574 ms 37588 KB Output is correct
25 Correct 469 ms 37708 KB Output is correct
26 Correct 522 ms 37736 KB Output is correct
27 Correct 561 ms 37552 KB Output is correct