#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[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});
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;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3420 KB |
Output is correct |
| 4 |
Runtime error |
6 ms |
2908 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3420 KB |
Output is correct |
| 4 |
Runtime error |
6 ms |
2908 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3420 KB |
Output is correct |
| 4 |
Runtime error |
6 ms |
2908 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
