Submission #1012073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012073		vjudge1	Sateliti (COCI20_satellti)	C++17	110 / 110	363 ms	84908 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;

    // 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 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]) % 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;


    int best = 0;
    for (int i = 1; i < vec.size(); i ++)
        if (cmp(vec[i], vec[best]))
            best = i;

    int x = vec[best].first;
    int y = vec[best].second;

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

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 1; i < vec.size(); i ++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60