#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
ll mod = 1e9+7;
ll b = 31, b2 = 37;
ll add(ll a, ll b) {return (a+b)%mod;}
ll sub(ll a, ll b) {return (a+mod-b)%mod;}
ll mul(ll a, ll b) {return (a*b)%mod;}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
char c1;
// * is smaller than .
vector<vector<ll>> a(2*n+1,vector<ll>(2*m+1,0));
vector<vector<char>> o(2*n+1,vector<char>(2*m+1));
FOR(i,1,n+1) {
FOR(j,1,m+1) {
cin >> c1;
a[i][j] = a[i+n][j] = a[i][j+m] = a[i+n][j+m] = (c1=='.')+1;
o[i][j] = o[i+n][j] = o[i][j+m] = o[i+n][j+m] = c1;
}
}
int r = 1, c = 1;
vector<ll> exp(n+1,1), exp2(m+1,1);
F0R(i,n) {exp[i+1]=mul(exp[i],b);}
F0R(i,m) {exp2[i+1]=mul(exp2[i],b2);}
FOR(i,1,n+1) {
FOR(j,1,m+1) {
a[i][j] = mul(a[i][j],mul(exp[i],exp2[j]));
a[i][j] = sub(add(add(a[i][j],a[i-1][j]),a[i][j-1]),a[i-1][j-1]);
}
}
auto get = [&](int a1, int b1, int c1, int d1)->ll {
ll q1 = mul(a[a1-1][d1],exp[c1-a1+1]);
ll q3 = mul(a[c1][b1-1],exp2[d1-b1+1]);
ll q2 = mul(a[a1-1][b1-1],mul(exp[c1-a1+1],exp2[d1-b1+1]));
ll ret = add(sub(sub(a[c1][d1],q1),q3),q2);
return ret;
};
FOR(i,1,n+1) {
FOR(j,1,m+1) {
int l = 1, h = n*m, mid = (l+h)/2;
int work = 0;
while (l <= h) {
int flag = 1;
int div = mid/m, rem = mid%m;
if (div) {flag &= (get(i,j,i+div-1,j+m-1)==get(r,c,r+div-1,c+m-1));}
if (rem) {flag &= (get(i+div,j,i+div,j+rem-1)==get(r+div,c,r+div,c+rem-1));}
if (flag) {l = mid+1; work = mid;}
else {h = mid-1;}
mid = (l+h)/2;
}
if (work != n*m) {
work++;
if (o[i+work/m][j+work%m-1]<o[r+work/m][c+work%m-1]) {r = i; c = j;}
}
// side cases: nothing works, everything works (only have to consider second one)
}
}
F0R(i,n) {
F0R(j,m) {cout << o[i+r][j+c];} cout << '\n';
}
//cout << get(1,1,2,2) << '\n';
//cout << get(2,2,3,3) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
