oj.uz

Submission #692020

# Submission time Handle Problem Language Result Execution time Memory
692020 2023-02-01T05:05:08 Z Neos Sateliti (COCI20_satellti) C++14
110 / 110
 621 ms 37704 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;

#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define MASK(x) 1ll << (x)

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

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

int n, m;
ll pw[N], pw2[N], hsh[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++) {
            hsh[i][j] = (hsh[i - 1][j] * base1 % MOD + hsh[i][j - 1] * base2 % MOD) % MOD;
            (hsh[i][j] -= hsh[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 = (hsh[x][y] - hsh[a - 1][y] * pw[x - a + 1] % MOD - hsh[x][b - 1] * pw2[y - b + 1] + 1ll * MOD * MOD) % MOD;
    (ret += hsh[a - 1][b - 1] * pw[x - a + 1] % MOD * pw2[y - b + 1] % MOD + 1ll * MOD * MOD) %= MOD;
    return ret;
}

signed main() {
    fastIO;
    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();
    ii 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.fi, pos.se, pos.fi + mid - 1, pos.se + 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.fi, pos.se, pos.fi + ans - 1, pos.se + 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.fi + ans - 1][pos.se + ans1 - 1]) pos = {i, j};
        }
    for (int i = pos.fi; i < pos.fi + n; i++) {
        for (int j = pos.se; j < pos.se + m; j++)
            cout << a[i][j];
        cout << '\n';
    }
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 2 ms 920 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 2 ms 920 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 48 ms 6608 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 3912 KB Output is correct
11 Correct 44 ms 6628 KB Output is correct
12 Correct 47 ms 6744 KB Output is correct
13 Correct 47 ms 6844 KB Output is correct
14 Correct 49 ms 6828 KB Output is correct
15 Correct 46 ms 6840 KB Output is correct
16 Correct 53 ms 6824 KB Output is correct
17 Correct 49 ms 6840 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 2 ms 920 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 48 ms 6608 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 3912 KB Output is correct
11 Correct 44 ms 6628 KB Output is correct
12 Correct 47 ms 6744 KB Output is correct
13 Correct 47 ms 6844 KB Output is correct
14 Correct 49 ms 6828 KB Output is correct
15 Correct 46 ms 6840 KB Output is correct
16 Correct 53 ms 6824 KB Output is correct
17 Correct 49 ms 6840 KB Output is correct
18 Correct 568 ms 37532 KB Output is correct
19 Correct 10 ms 12628 KB Output is correct
20 Correct 9 ms 980 KB Output is correct
21 Correct 535 ms 37628 KB Output is correct
22 Correct 598 ms 37572 KB Output is correct
23 Correct 541 ms 37612 KB Output is correct
24 Correct 612 ms 37656 KB Output is correct
25 Correct 525 ms 37704 KB Output is correct
26 Correct 590 ms 37632 KB Output is correct
27 Correct 621 ms 37580 KB Output is correct