Submission #1206550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206550		_rain_	Sateliti (COCI20_satellti)	C++20	110 / 110	225 ms	28860 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)2000;
const int MOD=1e9+9;
const int base=9973;
	char c[N+2][N+2];
	
	int numrow,numcol;
	int length,need_row;

	void build_board(){
		for(int i=1;i<=numrow;++i){
			for(int j=numcol+1;j<=2*numcol;++j) {
				c[i][j]=c[i][j-numcol];
			}
		}
		for(int i=numrow+1;i<=2*numrow;++i){
			for(int j=1;j<=numcol;++j) {
				c[i][j]=c[i-numrow][j];
			}
		}
		for(int i=numrow+1;i<=2*numrow;++i){
			for(int j=numcol+1;j<=2*numcol;++j){
				c[i][j]=c[i-numrow][j-numcol];
			}
		}
		return;
	}
	
	
	int p[N+2];
	int cot[2][N+2][N+2];

		int Get(int t,int id,int l,int r){
			return ((LL)cot[t][id][r]-(LL)cot[t][id][l-1]*p[r-l+1]+(LL)MOD*MOD)%MOD;
		}

	//... COMPARE THE FUNCTION
		int cmp_cot(pair<int,int>a,pair<int,int>b){
			int low=1,high=need_row,p=0;
			while (low<=high){
				int mid=(low+high)/2;
				if (Get(1,a.second,a.first,a.first+mid-1)==Get(1,b.second,b.first,b.first+mid-1)){
					p=mid;
					low=mid+1;
				}
				else high=mid-1;
			}
			return p;
		}
		bool compares(pair<int,int>a,pair<int,int>b){
			int r=cmp_cot(a,b);
			if (r==need_row) return false;
			int low=1,high=length,p=0;
			while (low<=high){
				int mid=(low+high)/2;
				if (Get(0,a.first+r,a.second,a.second+mid-1)==Get(0,b.first+r,b.second,b.second+mid-1)){
					p=mid;
					low=mid+1;
				}
				else high=mid-1;
			}
			if (p==length) return false;
			return c[a.first+r][a.second+p]>c[b.first+r][b.second+p];
		}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
	
	cin>>numrow>>numcol;
	for(int i=1;i<=numrow;++i){
		for(int j=1;j<=numcol;++j){
			cin>>c[i][j];
		}
	}
	build_board();
	numrow=2*numrow;
	numcol=2*numcol;
	length=numcol/2;
	need_row=numrow/2;
	
	p[0]=1;
	for(int i=1;i<=N;++i) p[i]=(LL)p[i-1]*base%MOD;

	for(int i=1;i<=numrow;++i) {
		for(int j=1;j<=numcol;++j){
			cot[0][i][j]=((LL)cot[0][i][j-1]*base+c[i][j]-'a'+1)%MOD;
		}
	}
	for(int j=1;j<=length;++j){
		for(int i=1;i<=numrow;++i){
			int x=Get(0,i,j,j+length-1);
			cot[1][j][i]=((LL)cot[1][j][i-1]*base+x)%MOD;
		}
	}
	pair<int,int>final={1,1};
	for(int i=1;i<=need_row;++i){
		for(int j=1;j<=length;++j){
			if (compares(final,{i,j})) final={i,j};
		}
	}
	for(int i=final.first;i<=final.first+need_row-1;++i){
		for(int j=final.second;j<=final.second+length-1;++j){
			cout<<c[i][j];
		}
		cout<<'\n';
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:74:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:75:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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