oj.uz

Submission #1094204

# Submission time Handle Problem Language Result Execution time Memory
1094204 2024-09-29T00:34:49 Z hippo123 Sateliti (COCI20_satellti) C++17
110 / 110
 557 ms 37772 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)



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;
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    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:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 39 ms 9492 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 40 ms 9584 KB Output is correct
12 Correct 44 ms 9484 KB Output is correct
13 Correct 42 ms 9560 KB Output is correct
14 Correct 44 ms 9564 KB Output is correct
15 Correct 43 ms 9564 KB Output is correct
16 Correct 41 ms 9560 KB Output is correct
17 Correct 44 ms 9560 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 39 ms 9492 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 40 ms 9584 KB Output is correct
12 Correct 44 ms 9484 KB Output is correct
13 Correct 42 ms 9560 KB Output is correct
14 Correct 44 ms 9564 KB Output is correct
15 Correct 43 ms 9564 KB Output is correct
16 Correct 41 ms 9560 KB Output is correct
17 Correct 44 ms 9560 KB Output is correct
18 Correct 470 ms 37748 KB Output is correct
19 Correct 8 ms 12892 KB Output is correct
20 Correct 8 ms 2968 KB Output is correct
21 Correct 458 ms 37752 KB Output is correct
22 Correct 554 ms 37772 KB Output is correct
23 Correct 449 ms 37712 KB Output is correct
24 Correct 544 ms 37716 KB Output is correct
25 Correct 455 ms 37756 KB Output is correct
26 Correct 512 ms 37768 KB Output is correct
27 Correct 557 ms 37760 KB Output is correct