oj.uz

Submission #1011805

# Submission time Handle Problem Language Result Execution time Memory
1011805 2024-07-01T08:53:22 Z vjudge1 Sateliti (COCI20_satellti) C++17
50 / 110
 707 ms 39600 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 992 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 992 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 60 ms 6996 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 52 ms 6916 KB Output is correct
12 Correct 49 ms 7028 KB Output is correct
13 Correct 52 ms 7000 KB Output is correct
14 Correct 53 ms 7000 KB Output is correct
15 Correct 59 ms 7004 KB Output is correct
16 Correct 59 ms 7004 KB Output is correct
17 Correct 60 ms 7140 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 992 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 60 ms 6996 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 52 ms 6916 KB Output is correct
12 Correct 49 ms 7028 KB Output is correct
13 Correct 52 ms 7000 KB Output is correct
14 Correct 53 ms 7000 KB Output is correct
15 Correct 59 ms 7004 KB Output is correct
16 Correct 59 ms 7004 KB Output is correct
17 Correct 60 ms 7140 KB Output is correct
18 Correct 687 ms 39600 KB Output is correct
19 Correct 11 ms 12636 KB Output is correct
20 Correct 11 ms 1116 KB Output is correct
21 Incorrect 707 ms 39528 KB Output isn't correct
22 Halted 0 ms 0 KB -