oj.uz

Submission #1012079

# Submission time Handle Problem Language Result Execution time Memory
1012079 2024-07-01T15:34:34 Z vjudge1 Sateliti (COCI20_satellti) C++17
110 / 110
 389 ms 37568 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 2005, p = 727, q = 101, mod = 1e9 + 9;
ll n, m, pref[N][N];
ll pwr_p[N], pwr_q[N], inv_p[N], inv_q[N];
char mat[N][N];

ll pwr(ll a, ll b){
    if (b == 0) return 1;
    ll val = pwr(a, b / 2);
    val = val * val % mod;

    if (b & 1) val = val * a % mod;
    return val;
}

inline bool cmp(pair<ll, ll> x, pair<ll, ll> y){
    ll ix = x.first;
    ll jx = x.second;
    ll iy = y.first;
    ll jy = y.second;

    ll l = -1;
    ll r = n;
    while (r - l > 1){
        ll mid = (l + r) / 2;
        
        ll ax = ix + mid, bx = jx + (m - 1);
        ll ay = iy + mid, by = jy + (m - 1);

        ll hsh_x = (pref[ax][bx] - pref[ax][bx - m] - pref[ax - mid - 1][bx] + pref[ax - mid - 1][bx - m]) % mod;
        hsh_x = (hsh_x * ((inv_p[ax - 1] * inv_q[bx - 1]) % mod)) % mod;

        ll hsh_y = (pref[ay][by] - pref[ay][by - m] - pref[ay - mid - 1][by] + pref[ay - mid - 1][by - m]) % mod;
        hsh_y = (hsh_y * ((inv_p[ay - 1] * inv_q[by - 1]) % mod)) % mod;

        hsh_x = (hsh_x + mod) % mod;
        hsh_y = (hsh_y + mod) % mod;

        if (hsh_x == hsh_y)
            l = mid;
        else
            r = mid;
    }

    if (r == n) return 1;

    ll row = r;

    l = -1;
    r = m;

    while (r - l > 1){
        ll mid = (l + r) / 2;

        ll ax = ix + row, bx = jx + mid;
        ll ay = iy + row, by = jy + mid;

        ll hsh_x = (pref[ax][bx] - pref[ax][bx - mid - 1] - pref[ax - 1][bx] + pref[ax - 1][bx - mid - 1]) % mod;
        hsh_x = (hsh_x * ((inv_p[ax - 1] * inv_q[bx - 1]) % mod)) % mod;

        ll hsh_y = (pref[ay][by] - pref[ay][by - mid - 1] - pref[ay - 1][by] + pref[ay - 1][by - mid - 1]) % mod;
        hsh_y = (hsh_y * ((inv_p[ay - 1] * inv_q[by - 1]) % mod)) % mod;

        hsh_x = (hsh_x + mod) % mod;
        hsh_y = (hsh_y + mod) % mod;

        if (hsh_x == hsh_y)
            l = mid;
        else
            r = mid;
    }

    ll col = r;

    return (mat[ix + row][jx + col] <= mat[iy + row][jy + col]);
}

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

    pwr_p[0] = pwr_q[0] = inv_p[0] = inv_q[0] = 1;
    for (ll i = 1; i < N; i ++){
        pwr_p[i] = pwr_p[i - 1] * p % mod;
        pwr_q[i] = pwr_q[i - 1] * q % mod;
        inv_p[i] = pwr(pwr_p[i], mod - 2);
        inv_q[i] = pwr(pwr_q[i], mod - 2);
    }

    cin >> n >> m;
    for (ll i = 1; i <= n; i ++){
        for (ll j = 1; j <= m; j ++){
            cin >> mat[i][j];
            mat[i + n][j] = mat[i + n][j + m] = mat[i][j + m] = mat[i][j];
        }
    }

    for (ll i = 1; i <= 2 * n; i ++){
        for (ll j = 1; j <= 2 * m; j ++){
            ll val = (((pwr_p[i - 1] * pwr_q[j - 1]) % mod) * mat[i][j]) % mod;

            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
            pref[i][j] = (pref[i][j] + val + mod) % mod;
        }
    }

    int x = 1, y = 1;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (cmp({i, j}, {x, y}))
                x = i, y = j;

    for (ll i = x; i < x + n; i ++){
        for (ll j = y; j < y + m; j ++)
            cout << mat[i][j];
        cout << endl;
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 26 ms 6820 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 4 ms 3928 KB Output is correct
11 Correct 26 ms 6748 KB Output is correct
12 Correct 48 ms 6856 KB Output is correct
13 Correct 27 ms 7004 KB Output is correct
14 Correct 43 ms 7256 KB Output is correct
15 Correct 29 ms 7000 KB Output is correct
16 Correct 26 ms 7004 KB Output is correct
17 Correct 30 ms 7004 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 26 ms 6820 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 4 ms 3928 KB Output is correct
11 Correct 26 ms 6748 KB Output is correct
12 Correct 48 ms 6856 KB Output is correct
13 Correct 27 ms 7004 KB Output is correct
14 Correct 43 ms 7256 KB Output is correct
15 Correct 29 ms 7000 KB Output is correct
16 Correct 26 ms 7004 KB Output is correct
17 Correct 30 ms 7004 KB Output is correct
18 Correct 314 ms 37464 KB Output is correct
19 Correct 9 ms 12636 KB Output is correct
20 Correct 6 ms 1116 KB Output is correct
21 Correct 299 ms 37368 KB Output is correct
22 Correct 389 ms 37360 KB Output is correct
23 Correct 302 ms 37376 KB Output is correct
24 Correct 359 ms 37460 KB Output is correct
25 Correct 299 ms 37360 KB Output is correct
26 Correct 371 ms 37568 KB Output is correct
27 Correct 357 ms 37320 KB Output is correct