oj.uz

Submission #705127

# Submission time Handle Problem Language Result Execution time Memory
705127 2023-03-03T12:13:21 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
50 / 110
 3000 ms 147212 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))%mod[0];
        ps[1][i][j]=(ps[1][i-1][j]+gthsh(1,i,j-m+1,j))%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 2516 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 16 ms 2588 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 21 ms 2796 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 16 ms 2588 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 21 ms 2796 KB Output is correct
8 Correct 56 ms 23408 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 8 ms 12500 KB Output is correct
11 Correct 45 ms 23416 KB Output is correct
12 Correct 584 ms 23824 KB Output is correct
13 Correct 58 ms 24268 KB Output is correct
14 Correct 136 ms 24180 KB Output is correct
15 Correct 45 ms 24180 KB Output is correct
16 Correct 62 ms 24196 KB Output is correct
17 Correct 897 ms 24184 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 16 ms 2588 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 21 ms 2796 KB Output is correct
8 Correct 56 ms 23408 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 8 ms 12500 KB Output is correct
11 Correct 45 ms 23416 KB Output is correct
12 Correct 584 ms 23824 KB Output is correct
13 Correct 58 ms 24268 KB Output is correct
14 Correct 136 ms 24180 KB Output is correct
15 Correct 45 ms 24180 KB Output is correct
16 Correct 62 ms 24196 KB Output is correct
17 Correct 897 ms 24184 KB Output is correct
18 Correct 528 ms 146988 KB Output is correct
19 Correct 22 ms 42104 KB Output is correct
20 Correct 9 ms 3284 KB Output is correct
21 Correct 546 ms 147212 KB Output is correct
22 Execution timed out 3046 ms 146276 KB Time limit exceeded
23 Halted 0 ms 0 KB -