Submission #1011829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011829		vjudge1	Sateliti (COCI20_satellti)	C++17	0 / 110	5 ms	1628 KiB

Main

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

    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[ix - 1] * inv_q[jx - 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[iy - 1] * inv_q[jy - 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 ++){
            a[i][j] = (pwr_p[i - 1] * pwr_q[j - 1] * 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;
        }
    }

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

    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: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60