oj.uz

Submission #1015480

# Submission time Handle Problem Language Result Execution time Memory
1015480 2024-07-06T11:29:12 Z vjudge1 Sateliti (COCI20_satellti) C++17
10 / 110
 39 ms 11612 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 2005;
const int p = 727, q = 311, mod = 1e9 + 9;

int pre[M][M],pw[M],ivp[M],qw[M],ivq[M];
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]%mod*ivq[y]%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()
{
	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-1]%mod*qw[j-1]%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 2 ms 4952 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5056 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5056 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 35 ms 11604 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 33 ms 11540 KB Output is correct
12 Incorrect 39 ms 11612 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5056 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 35 ms 11604 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 33 ms 11540 KB Output is correct
12 Incorrect 39 ms 11612 KB Output isn't correct
13 Halted 0 ms 0 KB -