oj.uz

Submission #705031

# Submission time Handle Problem Language Result Execution time Memory
705031 2023-03-03T08:42:04 Z 1075508020060209tc Sateliti (COCI20_satellti) C++17
0 / 110
 2 ms 1876 KB 
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int mod[2]={1000000009,998244353};
int n;int m;
string tgr[2010];
int gr[2010][2010];
int hsh[2][2010][2010];
int tme[2][5010];
int ansx;int ansy;
void precalc(){
tme[0][0]=1;tme[1][0]=1;
for(int i=1;i<=5000;i++){
    tme[0][i]=(tme[0][i-1]*31)%mod[0];
    tme[1][i]=(tme[0][i-1]*53)%mod[1];
}
}

void hshclc(int id){
for(int i=1;i<=n+n;i++){
    for(int j=1;j<=m+m;j++){
        hsh[id][i][j]=(hsh[id][i][j-1]+tme[id][j]*gr[i][j])%mod[id];
    }
}
}

int gthsh(int id,int i,int l,int r){
int ret=(hsh[id][i][r]-hsh[id][i][l-1]+mod[id])%mod[id];
ret=ret*tme[id][m+m-r]%mod[id];
return ret;
}
int same(int i,int l,int r,int j,int a,int b){
if(gthsh(0,i,l,r)!=gthsh(0,j,a,b)){return 0;}
if(gthsh(1,i,l,r)!=gthsh(1,j,a,b)){return 0;}
return 1;
}

int ok(int mi,int x,int y){

for(int i=1;i<=(mi/m);i++){
    if(!same(x+i-1,y,y+m-1,ansx+i-1,ansy,ansy+m-1)){return 0;}
}
int len=mi%m;
if(len==0){return 1;}
if(!same(x+mi/m,y,y+len-1,ansx+mi/m,ansy,ansy+len-1)){return 0;}
return 1;
}


int smaller(int x,int y){

int l=0;int r=n*m;
while(l<r){
    int mi=l+(r-l+1)/2;
    if(ok(mi,x,y)){
        l=mi;
    }else{
        r=mi-1;
    }
}
if(l==n*m){return 0;}
l++;
int ad=l%m-1;if(ad==-1){ad=m-1;}
if(gr[x+(l-1)/m ][y+ad]<gr[ansx+(l-1)/m ][ansy+ad]){return 1;}
return 0;
}


signed main(){




cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>tgr[i];
    tgr[i]=tgr[i]+tgr[i];
    tgr[i]="*"+tgr[i];
    tgr[i+n]=tgr[i];
}

for(int i=1;i<=n+n;i++){
    for(int j=1;j<=m+m;j++){
        if(tgr[i][j]=='*'){
            gr[i][j]=1;
        }else{
            gr[i][j]=2;
        }
    }
}
precalc();
hshclc(0);
hshclc(1);
ansx=1;ansy=1;


for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(smaller(i,j)){
            ansx=i;ansy=j;
        }
    }
}

for(int i=ansx;i<=ansx+n-1;i++){
    for(int j=ansy;j<=ansy+m-1;j++){
        cout<<tgr[i][j];
    }cout<<endl;
}



}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -