#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pr pair<int, int>
#define f first
#define s second
#define ndim 2010
const ll a =2;
const ll b =3;
const ll mod=(1LL<<60)-1;
int n, m;
vector<ll> pa(ndim);
vector<ll> pb(ndim);
vector<vector<ll>> hs(ndim, vector<ll> (ndim));
vector<vector<int>> d(ndim, vector<int> (ndim));
static __int128 mul(ll a, ll b) {return (__int128) a*b;}
static ll mod_mul(ll a, ll b, ll mod) { return mul(a, b)%mod;}
void hashfun(){
pa[0]=1;
for (int i=0; i<2001; i++) pa[i+1]=mod_mul(pa[i], a, mod);
pb[0]=1;
for (int i=0; i<2001; i++) pb[i+1]=mod_mul(pb[i], b, mod);
hs[0][0]=0;
for (int i=0; i<2001; i++) {hs[i][0]=0; hs[0][i]=0;}
for (int i=0; i<2*n; i++){// row
for (int j=0; j<2*m; j++){
hs[i+1][j+1]=(mod_mul(hs[i][j+1], a, mod)+mod_mul(hs[i+1][j], b, mod))%mod;
hs[i+1][j+1]=((hs[i+1][j+1]-mod_mul(mod_mul(hs[i][j], a, mod), b, mod))%mod+mod)%mod;
hs[i+1][j+1]=(hs[i+1][j+1]-d[i][j])%mod;
//(hsh[i][j] -= hsh[i - 1][j - 1] * base1 * base2 % MOD + a[i][j] - 'a' + 1) %= MOD;
}
}
}
ll hashval(int bx, int by, int ex, int ey){
ll temp=hs[ex+1][ey+1];
ll temp1=mod_mul(hs[bx][ey+1], pa[ex-bx+1], mod);
ll temp2=mod_mul(hs[ex+1][by], pb[ey-by+1], mod);
ll temp3=mod_mul(mod_mul(hs[bx][by], pa[ex-bx+1], mod), pb[ey-by+1], mod);
temp=(((temp-temp1+mod)%mod+mod-temp2)%mod+temp3+mod)%mod;
return temp;
}
int main(){
cin>>n>>m;
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
char s; cin>>s;
if(s=='*') d[i][j]=0;
else d[i][j]=1;
d[i+n][j]=d[i][j]; d[i][j+m]=d[i][j]; d[i+n][j+m]=d[i][j];
}
}
hashfun();
pr pos={0, 0}; // initial position
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
//
//cout<< " i/j= "<<i<<" "<<j<<endl;
int lft=1; int rht=n; int ans=-1;
while(lft<rht){
int mid=(lft+rht)/2;
ll temp=hashval(i, j, i+mid-1,j+n-1);
ll temp2=hashval(pos.f, pos.s, pos.f+mid-1, pos.s+n-1);
if(!(temp==temp2)) {
rht=mid; ans=mid;
}
else {
lft=mid+1;
}
}
//cout<<" ans= "<<ans<<endl;
if(ans==-1) continue;
lft=1; rht=m; int ans2=-1;
while(lft<rht){
int mid=(lft+rht)/2;
ll temp =hashval(i, j, i+ans-1, j+mid-1);
ll temp2=hashval(pos.f, pos.s, pos.f+ans-1, pos.s+mid-1);
if(!(temp==temp2)) {
rht=mid; ans2=mid;
}
else {
lft=mid+1;
}
}
if(ans2==-1) continue;
if(d[i+ans-1][j+ans2-1]<d[pos.f+ans-1][pos.s+ans2-1]){
pos.f=i; pos.s=j;
}
}
}
for (int i=0; i<n; i++){
for (int j=0; j<m; j++) {
if(d[i+pos.f][j+pos.s]==1) cout<<'.';
else cout<<'*';
}
cout<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47952 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 3 |
Correct |
26 ms |
47972 KB |
Output is correct |
| 4 |
Correct |
27 ms |
47952 KB |
Output is correct |
| 5 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 6 |
Correct |
29 ms |
47960 KB |
Output is correct |
| 7 |
Correct |
25 ms |
47876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47952 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 3 |
Correct |
26 ms |
47972 KB |
Output is correct |
| 4 |
Correct |
27 ms |
47952 KB |
Output is correct |
| 5 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 6 |
Correct |
29 ms |
47960 KB |
Output is correct |
| 7 |
Correct |
25 ms |
47876 KB |
Output is correct |
| 8 |
Correct |
107 ms |
48164 KB |
Output is correct |
| 9 |
Incorrect |
25 ms |
48216 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47952 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 3 |
Correct |
26 ms |
47972 KB |
Output is correct |
| 4 |
Correct |
27 ms |
47952 KB |
Output is correct |
| 5 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 6 |
Correct |
29 ms |
47960 KB |
Output is correct |
| 7 |
Correct |
25 ms |
47876 KB |
Output is correct |
| 8 |
Correct |
107 ms |
48164 KB |
Output is correct |
| 9 |
Incorrect |
25 ms |
48216 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
