oj.uz

Submission #705125

# Submission time Handle Problem Language Result Execution time Memory
705125 2023-03-03T12:09:18 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
10 / 110
 46 ms 23420 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
const int mod[2]={1000000007,998244353};
int n;int m;
string tgr[2010];
int gr[2010][2010];
int hsh[2][2010][2010];
int tme[2][6010];
int ansx;int ansy;
void precalc(){
tme[0][0]=1;tme[1][0]=1;
for(int i=1;i<=6002;i++){
    tme[0][i]=(tme[0][i-1]*31ll)%mod[0];
    tme[1][i]=(tme[1][i-1]*53ll)%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 ps[2][3010][3010];

void calcps(){

for(int i=1;i<=n+n;i++){
    for(int j=m;j<=m+m;j++){
        ps[0][i][j]=(ps[0][i-1][j]+gthsh(0,i,j-m+1,j)*tme[0][i])%mod[0];
        ps[1][i][j]=(ps[1][i-1][j]+gthsh(1,i,j-m+1,j)*tme[1][i])%mod[1];
    }
}


}

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 va=(ps[0][x+(mi/m)-1][y+m-1]-ps[0][x-1][y+m-1]+mod[0])%mod[0];
int vb=(ps[0][ansx+(mi/m)-1][ansy+m-1]-ps[0][ansx-1][ansy+m-1]+mod[0])%mod[0];
va=va*tme[0][3000-(x+(mi/m)-1)]%mod[0];
va=vb*tme[0][3000-(ansx+(mi/m)-1)]%mod[0];
//if(va!=vb){return 0;}

 va=(ps[1][x+(mi/m)-1][y+m-1]-ps[1][x-1][y+m-1]+mod[1])%mod[1];
 vb=(ps[1][ansx+(mi/m)-1][ansy+m-1]-ps[1][ansx-1][ansy+m-1]+mod[1])%mod[1];
va=va*tme[1][3000-(x+(mi/m)-1)]%mod[1];
va=vb*tme[1][3000-(ansx+(mi/m)-1)]%mod[1];
if(va!=vb){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.tie(0);
ios_base::sync_with_stdio(0);

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);
calcps();
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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2584 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 3 ms 2516 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2584 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 3 ms 2516 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 46 ms 23420 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Incorrect 6 ms 12500 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2584 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 3 ms 2516 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 46 ms 23420 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Incorrect 6 ms 12500 KB Output isn't correct
11 Halted 0 ms 0 KB -