oj.uz

Submission #1012066

# Submission time Handle Problem Language Result Execution time Memory
1012066 2024-07-01T15:23:24 Z vjudge1 Sateliti (COCI20_satellti) C++17
50 / 110
 3000 ms 84676 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, a[N][N], 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;

    // cout << ix << " " << jx << ", " << iy << " " << jy << endl;

    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 0;

    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 ++){
            a[i][j] = (((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] + a[i][j]) % mod;
            pref[i][j] = (pref[i][j] + mod) % mod;
        }
    }

    vector<pair<ll, ll>> vec;
    for (ll i = 1; i <= n; i ++)
        for (ll j = 1; j <= m; j ++)
            vec.push_back({i, j});

    // cout << "HERE" << endl;
    sort(vec.begin(), vec.end(), cmp);

    ll x = vec[0].first;
    ll y = vec[0].second;

    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 7 ms 1628 KB Output is correct
2 Correct 6 ms 1708 KB Output is correct
3 Correct 6 ms 1628 KB Output is correct
4 Correct 3 ms 1536 KB Output is correct
5 Correct 6 ms 1796 KB Output is correct
6 Correct 6 ms 1628 KB Output is correct
7 Correct 3 ms 1560 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1628 KB Output is correct
2 Correct 6 ms 1708 KB Output is correct
3 Correct 6 ms 1628 KB Output is correct
4 Correct 3 ms 1536 KB Output is correct
5 Correct 6 ms 1796 KB Output is correct
6 Correct 6 ms 1628 KB Output is correct
7 Correct 3 ms 1560 KB Output is correct
8 Correct 429 ms 14036 KB Output is correct
9 Correct 9 ms 860 KB Output is correct
10 Correct 4 ms 6492 KB Output is correct
11 Correct 421 ms 14040 KB Output is correct
12 Correct 408 ms 14036 KB Output is correct
13 Correct 451 ms 14292 KB Output is correct
14 Correct 413 ms 14296 KB Output is correct
15 Correct 423 ms 14296 KB Output is correct
16 Correct 431 ms 14368 KB Output is correct
17 Correct 451 ms 14296 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1628 KB Output is correct
2 Correct 6 ms 1708 KB Output is correct
3 Correct 6 ms 1628 KB Output is correct
4 Correct 3 ms 1536 KB Output is correct
5 Correct 6 ms 1796 KB Output is correct
6 Correct 6 ms 1628 KB Output is correct
7 Correct 3 ms 1560 KB Output is correct
8 Correct 429 ms 14036 KB Output is correct
9 Correct 9 ms 860 KB Output is correct
10 Correct 4 ms 6492 KB Output is correct
11 Correct 421 ms 14040 KB Output is correct
12 Correct 408 ms 14036 KB Output is correct
13 Correct 451 ms 14292 KB Output is correct
14 Correct 413 ms 14296 KB Output is correct
15 Correct 423 ms 14296 KB Output is correct
16 Correct 431 ms 14368 KB Output is correct
17 Correct 451 ms 14296 KB Output is correct
18 Execution timed out 3097 ms 84676 KB Time limit exceeded
19 Halted 0 ms 0 KB -