Submission #692020

#	Time	Username	Problem	Language	Result	Execution time	Memory
692020		Neos	Sateliti (COCI20_satellti)	C++14	110 / 110	621 ms	37704 KiB

Main

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

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

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;
    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 (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |                 int mid = l + r >> 1;
      |                           ~~^~~
Main.cpp:85:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |                 int mid = l + r >> 1;
      |                           ~~^~~

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