제출 #377825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377825		kshitij_sodani	Sateliti (COCI20_satellti)	C++14	110 / 110	1322 ms	225896 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,m;
llo it[2001][2001];
char aa[2001][2001];
llo pre[2001*2001];
llo pre2[2001*2001];
llo pre3[2001][2001];
llo pre5[2001*2001];
llo pre6[2001*2001];

llo pre4[2001][2001];

llo mod=1e9+7;
llo mod2=1e9+7;


llo ee(llo aa,llo bb,llo cc){
	if(bb==0){
		return 1;
	}
	llo ac=ee(aa,bb/2,cc);
	ac=(ac*ac)%cc;
	if(bb%2==1){
		ac=(ac*aa)%cc;
	}
	return ac;
}
llo cal(pair<llo,llo> bb,pair<llo,llo> cc){
	if(cc.a<bb.a or cc.b<bb.b){
		return 0;
	}
	llo cot=((pre3[cc.a+1][cc.b+1]-pre3[bb.a][cc.b+1]-pre3[cc.a+1][bb.b]+pre3[bb.a][bb.b]+mod+mod)%mod);
	while(cot>=mod){
		cot-=mod;
	}
	return  (cot*pre2[bb.a*m+bb.b])%mod;
}
llo cal2(pair<llo,llo> bb,pair<llo,llo> cc){
	if(cc.a<bb.a or cc.b<bb.b){
		return 0;
	}
	//cout<<bb.a<<",,"<<bb.b<<endl;
	//cout<<cc.a<<",,"<<cc.b<<endl;
	llo cot=(pre4[cc.a+1][cc.b+1]-pre4[bb.a][cc.b+1]-pre4[cc.a+1][bb.b]+pre4[bb.a][bb.b]+mod2+mod2);
	while(cot>=mod2){
		cot-=mod2;
	}
	//cout<<((((pre4[cc.a+1][cc.b+1]-pre4[bb.a][cc.b+1]-pre4[cc.a+1][bb.b]+pre4[bb.a][bb.b]+mod2+mod2)%mod2)*pre6[bb.a*m+bb.b])%mod2)<<endl;
	//cout<<pre4[cc.a+1][cc.b+1]<<endl;
	return  (cot*pre6[bb.a*m+bb.b])%mod2;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	pre[0]=1;
	
	cin>>n>>m;
	pre5[0]=1;
	for(llo i=1;i<=4*n*m;i++){
		pre[i]=(pre[i-1]*12192);

		pre[i]%=mod;
		pre5[i]=(pre5[i-1]*10000);
		
		pre5[i]%=mod2;
	}
	pre2[0]=1;
	pre6[0]=1;
	pre2[1]=ee(pre[1],mod-2,mod);
	pre6[1]=ee(pre5[1],mod2-2,mod2);
	for(int i=2;i<=4*n*m;i++){
		pre2[i]=(pre2[i-1]*pre2[1])%mod;
		pre6[i]=(pre6[i-1]*pre6[1])%mod;
	}
	//for(llo i=0;i<=4*n*m;i++){
		//pre2[i]=ee(pre[i],mod-2,mod);
	//	pre6[i]=ee(pre5[i],mod2-2,mod2);
	//}

	string ans="";
	for(llo i=0;i<n;i++){
		string s;
		cin>>s;
		for(llo j=0;j<m;j++){
			ans+=".";
			aa[i][j]=s[j];
			if(s[j]=='*'){
				it[i][j]=1;
			}
			else{
				it[i][j]=0;
			}
			it[i+n][j]=it[i][j];
			it[i+n][j+m]=it[i][j];
			it[i][j+m]=it[i][j];

			aa[i+n][j]=aa[i][j];
			aa[i+n][j+m]=aa[i][j];
			aa[i][j+m]=aa[i][j];
		}
	}
	/*for(llo i=0;i<=m;i++){
		cout<<pre[i]<<",,";
	}
	cout<<endl;*/
	for(llo i=1;i<=2*n;i++){
		for(llo j=1;j<=2*m;j++){
			pre3[i][j]=(pre3[i-1][j]+pre3[i][j-1]-pre3[i-1][j-1]+mod);
			if(it[i-1][j-1]==1){
				pre3[i][j]+=pre[(i-1)*m+j-1];
			}
			pre3[i][j]%=mod;
		}
	}

	for(llo i=1;i<=2*n;i++){
		for(llo j=1;j<=2*m;j++){
			pre4[i][j]=(pre4[i-1][j]+pre4[i][j-1]-pre4[i-1][j-1]+mod2);
			if(it[i-1][j-1]==1){
				pre4[i][j]+=pre5[(i-1)*m+j-1];
			}
			pre4[i][j]%=mod2;
		}
	}
	//cout<<cal2({1,1},{2,2})<<endl;
	/*for(llo i=1;i<=2*n;i++){
		for(llo j=1;j<=2*m;j++){
			pre4[i-1][j]=(pre4[i-1][j-1]);
			if(it[i-1][j-1]==1){
			//	cout<<i<<"//"<<j<<endl;
				pre4[i-1][j]+=pre5[j-1];
			}
			pre4[i-1][j]%=mod2;
		//	cout<<pre3[i-1][j]<<",,";
		}
		//cout<<endl;
	}*/
	//cout<<endl;
	//cout<<pre3[0][3]<<endl;
	pair<llo,llo> cur={0,0};
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(it[i][j]<it[cur.a][cur.b]){
				continue;
			}

			int low=0;
			int high=n;
			while(low<high-1){
				llo mid=(low+high)/2;
				if(cal(cur,{cur.a+mid-1,cur.b+m-1})==cal({i,j},{i+mid-1,j+m-1})){// and cal2(cur,{cur.a+mid-1,cur.b+m-1})==cal2({i,j},{i+mid-1,j+m-1})){
					low=mid;
				}
				else{
					high=mid;
				}
			}
			int ind=low;
			if(cal(cur,{cur.a+high-1,cur.b+m-1})==cal({i,j},{i+high-1,j+m-1})){//  and cal2(cur,{cur.a+high-1,cur.b+m-1})==cal2({i,j},{i+high-1,j+m-1})){
				ind=max(ind,high);
			}
			/*if(i==0 and j==1){
				cout<<ind<<endl;
			}*/
			if(ind<n){
				low=0;
				high=m;
				/*for(int k=0;k<m;k++){
					if(it[cur.a+ind][cur.b+k]!=it[i+ind][j+k]){
						if(it[i+ind][j+k]==1){
							cur={i,j};
						}
						break;
					}
				}
				continue;*/
				while(low<high-1){
					llo mid=(low+high)/2;
					if(cal({cur.a+ind,cur.b},{cur.a+ind,cur.b+mid-1})==cal({i+ind,j},{i+ind,j+mid-1}) and cal2({cur.a+ind,cur.b},{cur.a+ind,cur.b+mid-1})==cal2({i+ind,j},{i+ind,j+mid-1})){
						low=mid;
					}
					
					else{
						high=mid;
					}
				}
				int ind2=low;
				if(cal({cur.a+ind,cur.b},{cur.a+ind,cur.b+high-1})==cal({i+ind,j},{i+ind,j+high-1})  and cal2({cur.a+ind,cur.b},{cur.a+ind,cur.b+high-1})==cal2({i+ind,j},{i+ind,j+high-1})){
					
					ind2=max(ind2,high);
				}
				//if(i==0 and j==1){
				//	cout<<ind2<<endl;
				//	cout<<ind<<":"<<ind2<<endl;
				//}

				if(ind2<m){
					if(it[i+ind][j+ind2]==1){
					//	cout<<i<<":"<<j<<endl;
						cur={i,j};
					}
				}
			}
			

		}
	}



	/*for(llo i=0;i<2*n;i++){
		for(llo j=0;j<2*m;j++){
			cout<<it[i][j];
		}
		cout<<endl;
	}
*/
/*	for(llo j=0;j<m;j++){
		vector<string> ss;
		for(llo i=0;i<n;i++){
			string tt="";
			for(llo k=j;k<m;k++){
				tt+=aa[i][k];
			}
			for(llo k=0;k<j;k++){
				tt+=aa[i][k];
			}
			ss.pb(tt);
		}
		for(llo i=0;i<n;i++){
			string cur="";
			for(llo k=i;k<n;k++){
				cur+=ss[k];
			}
			for(llo k=0;k<i;k++){
				cur+=ss[k];
			}


			if(cur<ans){
			ans=cur;
		}

		}
		//sort(ss.begin(),ss.end());

		//cout<<"::"<<endl;
		
		//cout<<cur<<endl;
		

	}*/
	for(llo i=cur.a;i<cur.a+n;i++){
		for(llo j=cur.b;j<cur.b+m;j++){
			cout<<aa[i][j];
		}
		cout<<endl;
	}
	/*for(llo i=0;i<n*m;i++){
		cout<<ans[i];
		if(i%(m)==m-1){
			cout<<endl;
		}
	}
*/








 
	return 0;
}

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