Submission #446231

#	Time	Username	Problem	Language	Result	Execution time	Memory
446231		Jasiekstrz	Sateliti (COCI20_satellti)	C++17	110 / 110	884 ms	92624 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
const long long MOD=(1LL<<61)-1;
const long long B=997;
long long pot[4*N*N+10];
char c[2*N+10][2*N+10];
long long h1[2*N+10][2*N+10];
long long h2[2*N+10][2*N+10];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			c[i][m+j]=c[n+i][j]=c[n+i][m+j]=c[i][j];
		}
	}
	pot[0]=1;
	for(int i=1;i<=4*n*m;i++)
		pot[i]=((__int128)pot[i-1]*B)%MOD;
	for(int i=1;i<=2*n;i++)
	{
		for(int j=1;j<=2*m;j++)
			h1[i][j]=((__int128)h1[i][j-1]*B+(c[i][j]=='.'))%MOD;
	}
	for(int i=1;i<=2*n;i++)
	{
		for(int j=1;j<=m;j++)
			h2[i][j]=((__int128)h2[i-1][j]*pot[m]+h1[i][j+m-1]-(__int128)pot[m]*h1[i][j-1])%MOD;
	}

	auto hsh1=[](int x,int y,int d)
	{
		long long tmp=(h1[x][y+d-1]-(__int128)pot[d]*h1[x][y-1])%MOD;
		return (tmp+MOD)%MOD;
	};
	auto hsh2=[&m](int x,int y,int d)
	{
		long long tmp=(h2[x+d-1][y]-(__int128)pot[m*d]*h2[x-1][y])%MOD;
		return (tmp+MOD)%MOD;
	};
	auto comp=[&](pair<int,int> x,pair<int,int> y) // is x better than y
	{
		// matching rows
		int bg=0,en=n;
		while(bg<en)
		{
			int mid=(bg+en+1)/2;
			if(hsh2(x.fi,x.se,mid)==hsh2(y.fi,y.se,mid))
				bg=mid;
			else
				en=mid-1;
		}
		if(bg==n)
			return false;
		x.fi+=bg;
		y.fi+=bg;

		// matching columns
		bg=0,en=m;
		while(bg<en)
		{
			int mid=(bg+en+1)/2;
			if(hsh1(x.fi,x.se,mid)==hsh1(y.fi,y.se,mid))
				bg=mid;
			else
				en=mid-1;
		}
		return c[x.fi][x.se+bg]<c[y.fi][y.se+bg];
	};

	pair<int,int> ans={1,1};
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(comp({i,j},ans))
				ans={i,j};
		}
	}
	for(int i=ans.fi;i<ans.fi+n;i++)
	{
		for(int j=ans.se;j<ans.se+m;j++)
			cout<<c[i][j];
		cout<<"\n";
	}
	return 0;
}

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