oj.uz

Submission #1011839

# Submission time Handle Problem Language Result Execution time Memory
1011839 2024-07-01T09:29:09 Z vjudge1 Sateliti (COCI20_satellti) C++17
10 / 110
 37 ms 6744 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 2001;
const int mod = 1e9 + 7;

int pre[M][M],pw[M],ivp[M],qw[M],ivq[M],p,q;
char a[M][M];

int power(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

int hsh(int x,int y,int cnt,int m)
{
	int ans=0;
	if (cnt/m)
		ans=pre[x+cnt/m-1][y+m-1]-pre[x+cnt/m-1][y-1]-pre[x-1][y+m-1]+pre[x-1][y-1];
	if (cnt%m)
		ans+=pre[x+cnt/m][y+cnt%m-1]-pre[x+cnt/m][y-1]-pre[x-1][y+cnt%m-1]+pre[x-1][y-1];
	ans+=mod*4,ans%=mod;
	ans=ans*ivp[x-1]%mod*ivq[y-1]%mod;
	return ans;
}

bool comp(int x1,int y1,int x2,int y2,int n,int m)
{
	int s=0,e=n*m+1;
	while (s+1<e)
	{
		int mid=(s+e)/2;
		if (hsh(x1,y1,mid,m)==hsh(x2,y2,mid,m))
			s=mid;
		else
			e=mid;
	}
	if (s==n*m)
		return 0;
	return (a[x1+s/m][y1+s%m]=='*');
}

signed main()
{
	vector<int> pr={149,727,1451};
	vector<int> qr={211,307,4337};
	srand(time(NULL));
	p=pr[rand()%3];
	q=qr[rand()%3];
	int n,m;
	cin>>n>>m;
	n*=2,m*=2;
	for (int i=1;i<=n/2;i++)
		for (int j=1;j<=m/2;j++)
			cin>>a[i][j];
	for (int i=1;i<=n/2;i++)
		for (int j=m/2+1;j<=m;j++)
			a[i][j]=a[i][j-m/2];
	for (int i=n/2+1;i<=n;i++)
		for (int j=1;j<=m;j++)
			a[i][j]=a[i-n/2][j];
	pw[0]=qw[0]=1;
	for (int i=1;i<M;i++)
		pw[i]=pw[i-1]*p%mod,qw[i]=qw[i-1]*q%mod;
	ivp[M-1]=power(pw[M-1],mod-2),ivq[M-1]=power(qw[M-1],mod-2);
	for (int i=M-2;i>=0;i--)
		ivp[i]=ivp[i+1]*p%mod,ivq[i]=ivq[i+1]*q%mod;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
			pre[i][j]+=a[i][j]*pw[i]%mod*qw[j]%mod;
			pre[i][j]%=mod;
		}
	int idx=1,idy=1;
	for (int i=1;i+n/2-1<=n;i++)
		for (int j=1;j+m/2-1<=m;j++)
		{
			if (comp(i,j,idx,idy,n/2,m/2))
				idx=i,idy=j;
		}
	for (int i=idx;i<idx+n/2;i++)
	{
		for (int j=idy;j<idy+m/2;j++)
			cout<<a[i][j];
		cout<<endl;
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 32 ms 6696 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 3 ms 3932 KB Output is correct
11 Correct 35 ms 6740 KB Output is correct
12 Incorrect 37 ms 6744 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 32 ms 6696 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 3 ms 3932 KB Output is correct
11 Correct 35 ms 6740 KB Output is correct
12 Incorrect 37 ms 6744 KB Output isn't correct
13 Halted 0 ms 0 KB -