oj.uz

Submission #377825

# Submission time Handle Problem Language Result Execution time Memory
377825 2021-03-15T08:14:59 Z kshitij_sodani Sateliti (COCI20_satellti) C++14
110 / 110
 1322 ms 225896 KB 
//#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.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2412 KB Output is correct
2 Correct 3 ms 2156 KB Output is correct
3 Correct 4 ms 2156 KB Output is correct
4 Correct 2 ms 2156 KB Output is correct
5 Correct 3 ms 2284 KB Output is correct
6 Correct 2 ms 2284 KB Output is correct
7 Correct 3 ms 2412 KB Output is correct
8 Correct 66 ms 27884 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 7 ms 8812 KB Output is correct
11 Correct 40 ms 27940 KB Output is correct
12 Correct 105 ms 28140 KB Output is correct
13 Correct 44 ms 28780 KB Output is correct
14 Correct 109 ms 28780 KB Output is correct
15 Correct 41 ms 28780 KB Output is correct
16 Correct 109 ms 28908 KB Output is correct
17 Correct 112 ms 28780 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2412 KB Output is correct
2 Correct 3 ms 2156 KB Output is correct
3 Correct 4 ms 2156 KB Output is correct
4 Correct 2 ms 2156 KB Output is correct
5 Correct 3 ms 2284 KB Output is correct
6 Correct 2 ms 2284 KB Output is correct
7 Correct 3 ms 2412 KB Output is correct
8 Correct 66 ms 27884 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 7 ms 8812 KB Output is correct
11 Correct 40 ms 27940 KB Output is correct
12 Correct 105 ms 28140 KB Output is correct
13 Correct 44 ms 28780 KB Output is correct
14 Correct 109 ms 28780 KB Output is correct
15 Correct 41 ms 28780 KB Output is correct
16 Correct 109 ms 28908 KB Output is correct
17 Correct 112 ms 28780 KB Output is correct
18 Correct 824 ms 225128 KB Output is correct
19 Correct 25 ms 30700 KB Output is correct
20 Correct 17 ms 4716 KB Output is correct
21 Correct 388 ms 225768 KB Output is correct
22 Correct 1283 ms 225668 KB Output is correct
23 Correct 374 ms 225768 KB Output is correct
24 Correct 1289 ms 225768 KB Output is correct
25 Correct 380 ms 225768 KB Output is correct
26 Correct 1228 ms 225896 KB Output is correct
27 Correct 1322 ms 225400 KB Output is correct