Submission #1182798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182798		nikolashami	Sateliti (COCI20_satellti)	C++20	110 / 110	655 ms	64144 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const ll N=2e3+2;
ll a[N][N],n,m;

const ll T1=2,T2=3,mod=INT_MAX-170;
ll h[N][N],pw1[N],pw2[N],i1[N],i2[N];

ll pw(ll x,ll y){
	ll r=1;x%=mod;
	while(y){
		if(y&1)r=(r*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return r;
}

ll inv(ll x){
	return pw(x,mod-2);
}

ll get(ll r1,ll c1,ll r2,ll c2){
	ll ret=(h[r2][c2]-h[r1-1][c2]-h[r2][c1-1]+h[r1-1][c1-1]+2*mod)%mod;
	ret=(ret*i1[r1])%mod;
	ret=(ret*i2[c1])%mod;
	return ret;
}

bool cmp(const array<ll,2>&x,const array<ll,2>&y){
	array<ll,2>ans={0,0};
	ll l=1,r=n*m;
	while(l<=r){
		ll md=(l+r)/2,ii=(md+m-1)/m,jj=(md)%m;
		if(!jj)jj+=m;
		bool ok=!(ii>1&&(get(x[0],x[1],x[0]+ii-2,x[1]+m-1)!=get(y[0],y[1],y[0]+ii-2,y[1]+m-1)));
		ok&=(get(x[0]+ii-1,x[1],x[0]+ii-1,x[1]+jj-1)==get(y[0]+ii-1,y[1],y[0]+ii-1,y[1]+jj-1));
		if(ok)l=md+1;
		else{
			ans={ii-1,jj-1};
			r=md-1;
		}
	}
	return(a[x[0]+ans[0]][x[1]+ans[1]]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=m;++j){
    		char c;cin>>c;
    		a[i][j]=(c=='.');
    	}
    }

    for(int i=1;i<=2*n;++i){
    	for(int j=1;j<=2*m;++j)
    		a[i][j]=a[(i>n?i-n:i)][(j>m?j-m:j)];
    }

    pw1[0]=pw2[0]=1;
    i1[0]=i2[0]=inv(1);
    for(int i=1;i<N;++i){
    	pw1[i]=pw1[i-1]*T1%mod;
    	pw2[i]=pw2[i-1]*T2%mod;
    	i1[i]=inv(pw1[i]);
    	i2[i]=inv(pw2[i]);
    }

    for(int i=1;i<=2*n;++i){
    	for(int j=1;j<=2*m;++j){
    		ll x=(a[i][j]*pw1[i]%mod*pw2[j]%mod)+mod;
    		h[i][j]=(h[i-1][j]+h[i][j-1]-h[i-1][j-1]+x)%mod;
    	}
    }

    array<ll,2>mx={1,1};
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=m;++j)
    		if(!cmp({i,j},mx))mx={i,j};
    }

    for(int i=mx[0];i<mx[0]+n;++i){
    	for(int j=mx[1];j<mx[1]+m;++j)
    		cout<<(!a[i][j]?'*':'.');
    	cout<<'\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60