Submission #1262374

#TimeUsernameProblemLanguageResultExecution timeMemory
1262374askewwSateliti (COCI20_satellti)C++20
110 / 110
586 ms64036 KiB
#include <bits/stdc++.h> using namespace std; #define M(X) (X % P + P) % P template<typename T> using V = vector<T>; using ll = long long; const ll P = 1000000007LL, A = 10007LL, B = 10009LL; int n, m, ansl, ansr, lo, hi, mi, bi; char c; V<V<ll>> a, h; V<ll> pa, pb, pia, pib; ll inv; ll exp(ll b, ll e) { ll res = 1; while (e != 0) { if (e & 1) res = (res * b) % P; b = (b * b) % P; e >>= 1; } return res; } ll ch(ll a, ll b, ll c, ll d) { return M(M(M(h[c][d] - (a - 1 >= 0 ? h[a - 1][d] : 0) - (b - 1 >= 0 ? h[c][b - 1] : 0) + (a - 1 >= 0 && b - 1 >= 0 ? h[a - 1][b - 1] : 0)) * pia[a]) * pib[b]); } int main() { cin >> n >> m; inv = exp(A, P - 2); pa = pia = V<ll>(2 * n); pa[0] = pia[0] = 1; for (int i = 1; i < 2 * n; i++) { pa[i] = M(pa[i - 1] * A); pia[i] = M(pia[i - 1] * inv); } inv = exp(B, P - 2); pb = pib = V<ll>(2 * m); pb[0] = pib[0] = 1; for (int i = 1; i < 2 * m; i++) { pb[i] = M(pb[i - 1] * B); pib[i] = M(pib[i - 1] * inv); } a = V<V<ll>>(2 * n, V<ll>(2 * m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> c; if (c == '*') a[i][j] = 1; if (c == '.') a[i][j] = 2; a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j]; } } h = V<V<ll>>(2 * n, V<ll>(2 * m)); for (int i = 0; i < 2 * n; i++) { for (int j = 0; j < 2 * m; j++) { h[i][j] = M((i > 0 ? h[i - 1][j] : 0) + (j > 0 ? h[i][j - 1] : 0) - M((i > 0 && j > 0 ? h[i - 1][j - 1] : 0) + M(M(a[i][j] * pa[i]) * pb[j]))); } } ansl = ansr = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { lo = 0, hi = n; while (lo < hi) { mi = (lo + hi) / 2; if (ch(ansl, ansr, ansl + mi, ansr + m - 1) == ch(i, j, i + mi, j + m - 1)) { lo = mi + 1; } else { hi = mi; } } bi = hi; if (bi == n) continue; lo = 0, hi = m - 1; while (lo < hi) { mi = (lo + hi) / 2; if (ch(ansl, ansr, ansl + bi, ansr + mi) == ch(i, j, i + bi, j + mi)) { lo = mi + 1; } else { hi = mi; } } if (a[i + bi][j + hi] < a[ansl + bi][ansr + hi]) { ansl = i; ansr = j; } } } for (int ki = 0; ki < n; ki++) { for (int kj = 0; kj < m; kj++) { cout << (a[ansl + ki][ansr + kj] == 1 ? "*" : "."); } cout << '\n'; } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...