oj.uz

Submission #705132

# Submission time Handle Problem Language Result Execution time Memory
705132 2023-03-03T12:19:56 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
110 / 110
 738 ms 148300 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];
vb=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];
vb=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 3 ms 2772 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 2 ms 2584 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 2 ms 2584 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 46 ms 23380 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 6 ms 12500 KB Output is correct
11 Correct 44 ms 23416 KB Output is correct
12 Correct 60 ms 23792 KB Output is correct
13 Correct 47 ms 24184 KB Output is correct
14 Correct 56 ms 24268 KB Output is correct
15 Correct 52 ms 24180 KB Output is correct
16 Correct 52 ms 24184 KB Output is correct
17 Correct 59 ms 24184 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 2 ms 2584 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 46 ms 23380 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 6 ms 12500 KB Output is correct
11 Correct 44 ms 23416 KB Output is correct
12 Correct 60 ms 23792 KB Output is correct
13 Correct 47 ms 24184 KB Output is correct
14 Correct 56 ms 24268 KB Output is correct
15 Correct 52 ms 24180 KB Output is correct
16 Correct 52 ms 24184 KB Output is correct
17 Correct 59 ms 24184 KB Output is correct
18 Correct 556 ms 147112 KB Output is correct
19 Correct 28 ms 42324 KB Output is correct
20 Correct 10 ms 3284 KB Output is correct
21 Correct 514 ms 147216 KB Output is correct
22 Correct 738 ms 147420 KB Output is correct
23 Correct 507 ms 148192 KB Output is correct
24 Correct 656 ms 148272 KB Output is correct
25 Correct 508 ms 148300 KB Output is correct
26 Correct 607 ms 148192 KB Output is correct
27 Correct 722 ms 148172 KB Output is correct