제출 #377825

#제출 시각아이디문제언어결과실행 시간메모리
377825kshitij_sodaniSateliti (COCI20_satellti)C++14
110 / 110
1322 ms225896 KiB
//#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...