Submission #1011805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011805		vjudge1	Sateliti (COCI20_satellti)	C++17	50 / 110	707 ms	39600 KiB

Main

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

#define int long long
int const N=1005;
int const mod=1e9+7;
int const A=141;
int const B=727;
string s[N];
bool mat[2*N][2*N];
int pre_hash[2*N][2*N];
int pwA[N],pwB[N],invA[N],invB[N];
int power(int a,int b){
	if(b==0)
		return 1;
	if(b==1)
		return a;
	int p=power(a,b/2);
	p=(p*p)%mod;
	if(b&1)
		p=(p*a)%mod;
	return p%mod;
}
void precompute(){
	pwA[0]=1;
	pwB[0]=1;
	invA[0]=1;
	invB[0]=1;
	for (int i = 1; i < N; ++i)
	{
		pwA[i]=(pwA[i-1]*A)%mod;
		pwB[i]=(pwB[i-1]*B)%mod;
		invA[i]=power(pwA[i],mod-2)%mod;
		invB[i]=power(pwB[i],mod-2)%mod;
		// cout<<invA[i]<<' '<<invB[i]<<endl;
	}
}
int make_hash(int x1,int y1,int x2,int y2){
	x1--;y1--;
	int hsh=(pre_hash[x2][y2]-((pre_hash[x1][y2]+pre_hash[x2][y1])%mod))%mod;
	// cout<<hsh<<endl;
	hsh=(hsh+mod)%mod;
	hsh=(hsh+pre_hash[x1][y1])%mod;
	// cout<<hsh<<endl;
	hsh=(hsh*invA[x1])%mod;
	hsh=(hsh*invB[y1])%mod;
	return hsh;
}
signed main(){
	precompute();
	int n,m;
	cin>>n>>m;
	for (int i = 1; i <=n; ++i){
		cin>>s[i];
		for (int j = 1; j <=m; ++j)
			mat[i][j]=mat[i+n][j]=mat[i][j+m]=mat[i+n][j+m]=(s[i][j-1]=='.');
	}
	for(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*m;j++){
			pre_hash[i][j]=mat[i][j]*((pwA[i]*pwB[j])%mod);
			pre_hash[i][j]+=((((pre_hash[i-1][j]+pre_hash[i][j-1])%mod)-(pre_hash[i-1][j-1]))+mod)%mod;
			pre_hash[i][j]%=mod;
			// cout<<pre_hash[i][j]<<' ';
		}
		// cout<<endl;
	}
	int x=1,y=1;
	// cout<<invB[1]<<endl;
	// cout<<make_hash(x,y,x+n-1,y+m-1)<<endl<<make_hash(1,2,n,m+1)<<endl;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(make_hash(x,y,(x+n)-1,(y+m)-1)==make_hash(i,j,(i+n)-1,(j+m)-1)){
				// cout<<"NO"<<endl;
				// cout<<x<<' '<<y<<' '<<(x+n)-1<<' '<<(y+m)-1<<endl;
				// cout<<i<<' '<<j<<' '<<(i+n)-1<<' '<<(j+m)-1<<endl;
				continue;
			}
			int low=-1,high=n-1;
			while(high-low>1){
				int mid=(high+low)/2;
				if(make_hash(x,y,x+mid,y+m-1)==make_hash(i,j,i+mid,j+m-1))
					low=mid;
				else
					high=mid;
			}
			int r=high;
			low=-1,high=m-1;
			while(high-low>1){
				int mid=(high+low)/2;
				if(make_hash(x+r,y,x+r,y+mid)==make_hash(i+r,j,i+r,j+mid))
					low=mid;
				else
					high=mid;
			}
			int c=high;
			if(mat[i+r][j+c]<mat[x+r][y+c]){
				// cout<<"Switch"<<endl;
				x=i;
				y=j;
			}
			// cout<<x<<' '<<y<<endl;
		}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(mat[i+x][j+y])
				cout<<'.';
			else
				cout<<'*';
		}
		cout<<endl;
	}
	return 0;
}

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