Submission #1094204

#TimeUsernameProblemLanguageResultExecution timeMemory
1094204hippo123Sateliti (COCI20_satellti)C++17
110 / 110
557 ms37772 KiB
#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) 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; if (fopen("test.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } 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:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...