oj.uz

Submission #445981

# Submission time Handle Problem Language Result Execution time Memory
445981 2021-07-20T10:28:30 Z Jasiekstrz Sateliti (COCI20_satellti) C++17
10 / 110
 181 ms 5076 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
char c[N+10][N+10];
int tab[N+10][N+10];
int tmptab[N+10][N+10];
int ord[N+10][N+10];
int val[2*N*N+N+10];
int nval[2*N*N+N+10];
int srt[2*N*N+10];
void kmr(int n,int m)
{
	auto id=[&m](int x,int y)
	{
		return (x-1)*2*m+y;
	};

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=2*m;j++)
		{
			srt[id(i,j)]=id(i,j);
			val[id(i,j)]=tab[i][(j-1)%m+1];
		}
	}

	auto step_kmr=[&n,&m](int pot)
	{
		sort(srt+1,srt+n*2*m+1,[&pot](int a,int b){ 
				return (val[a]<val[b] || (val[a]==val[b] && val[a+pot]<val[b+pot])); });
		for(int i=1,it=0;i<=n*2*m;i++)
		{
			if(val[srt[i]]==val[srt[i-1]] && val[srt[i]+pot]==val[srt[i-1]+pot])
				nval[srt[i]]=it;
			else
				nval[srt[i]]=++it;
		}
		for(int i=1;i<=n*2*m;i++)
			val[i]=nval[i];
		return;
	};

	int pot;
	for(pot=2;pot<m;pot*=2)
		step_kmr(pot/2);
	pot/=2;
	step_kmr(m-pot);

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			tab[i][j]=val[id(i,j)];
	}
	return;
}
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];
			tab[i][j]=c[i][j];
		}
	}

	auto rot=[&n,&m]()
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
				tmptab[i][j]=tab[i][j];
		}
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
				tab[i][j]=tmptab[j][i];
		}
		return;
	};

	kmr(n,m);

	//for(int i=1;i<=n;i++)
	//{
	//	for(int j=1;j<=m;j++)
	//		cerr<<tab[i][j]<<" ";
	//	cerr<<"\n";
	//}
	
	rot();
	kmr(m,n);
	rot();

	pair<int,int> g={1,1};
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(tab[i][j]<tab[g.fi][g.se])
				g={i,j};
		}
	}

	for(int i=g.fi;i<g.fi+n;i++)
	{
		for(int j=g.se;j<g.se+m;j++)
			cout<<c[(i-1)%n+1][(j-1)%m+1];
		cout<<"\n";
	}
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 181 ms 5076 KB Output is correct
9 Correct 4 ms 1612 KB Output is correct
10 Incorrect 2 ms 2892 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 181 ms 5076 KB Output is correct
9 Correct 4 ms 1612 KB Output is correct
10 Incorrect 2 ms 2892 KB Output isn't correct
11 Halted 0 ms 0 KB -