oj.uz

Submission #705126

# Submission time Handle Problem Language Result Execution time Memory
705126 2023-03-03T12:09:52 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
50 / 110
 3000 ms 147948 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 2516 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 17 ms 2580 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 26 ms 2772 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 17 ms 2580 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 26 ms 2772 KB Output is correct
8 Correct 38 ms 23416 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 6 ms 12500 KB Output is correct
11 Correct 41 ms 23500 KB Output is correct
12 Correct 562 ms 23892 KB Output is correct
13 Correct 50 ms 24276 KB Output is correct
14 Correct 128 ms 24276 KB Output is correct
15 Correct 38 ms 24344 KB Output is correct
16 Correct 55 ms 24280 KB Output is correct
17 Correct 902 ms 24276 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 17 ms 2580 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 26 ms 2772 KB Output is correct
8 Correct 38 ms 23416 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 6 ms 12500 KB Output is correct
11 Correct 41 ms 23500 KB Output is correct
12 Correct 562 ms 23892 KB Output is correct
13 Correct 50 ms 24276 KB Output is correct
14 Correct 128 ms 24276 KB Output is correct
15 Correct 38 ms 24344 KB Output is correct
16 Correct 55 ms 24280 KB Output is correct
17 Correct 902 ms 24276 KB Output is correct
18 Correct 484 ms 147516 KB Output is correct
19 Correct 23 ms 42196 KB Output is correct
20 Correct 8 ms 3236 KB Output is correct
21 Correct 482 ms 147948 KB Output is correct
22 Execution timed out 3076 ms 146808 KB Time limit exceeded
23 Halted 0 ms 0 KB -