oj.uz

Submission #446231

# Submission time Handle Problem Language Result Execution time Memory
446231 2021-07-21T10:17:02 Z Jasiekstrz Sateliti (COCI20_satellti) C++17
110 / 110
 884 ms 92624 KB 
#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.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 2 ms 1356 KB Output is correct
3 Correct 2 ms 1352 KB Output is correct
4 Correct 2 ms 1356 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 67 ms 13040 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 4 ms 6268 KB Output is correct
11 Correct 70 ms 13032 KB Output is correct
12 Correct 71 ms 13228 KB Output is correct
13 Correct 73 ms 13472 KB Output is correct
14 Correct 71 ms 13508 KB Output is correct
15 Correct 71 ms 13484 KB Output is correct
16 Correct 73 ms 13620 KB Output is correct
17 Correct 71 ms 13472 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 2 ms 1356 KB Output is correct
3 Correct 2 ms 1352 KB Output is correct
4 Correct 2 ms 1356 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 67 ms 13040 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 4 ms 6268 KB Output is correct
11 Correct 70 ms 13032 KB Output is correct
12 Correct 71 ms 13228 KB Output is correct
13 Correct 73 ms 13472 KB Output is correct
14 Correct 71 ms 13508 KB Output is correct
15 Correct 71 ms 13484 KB Output is correct
16 Correct 73 ms 13620 KB Output is correct
17 Correct 71 ms 13472 KB Output is correct
18 Correct 848 ms 92484 KB Output is correct
19 Correct 16 ms 21068 KB Output is correct
20 Correct 14 ms 1996 KB Output is correct
21 Correct 804 ms 92592 KB Output is correct
22 Correct 873 ms 92572 KB Output is correct
23 Correct 820 ms 92584 KB Output is correct
24 Correct 863 ms 92576 KB Output is correct
25 Correct 802 ms 92624 KB Output is correct
26 Correct 844 ms 92604 KB Output is correct
27 Correct 884 ms 92424 KB Output is correct