oj.uz

Submission #705130

# Submission time Handle Problem Language Result Execution time Memory
705130 2023-03-03T12:18:09 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
50 / 110
 3000 ms 147324 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 17 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 18 ms 2792 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 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 18 ms 2792 KB Output is correct
8 Correct 45 ms 23472 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 6 ms 12532 KB Output is correct
11 Correct 45 ms 23464 KB Output is correct
12 Correct 562 ms 23824 KB Output is correct
13 Correct 55 ms 24268 KB Output is correct
14 Correct 132 ms 24176 KB Output is correct
15 Correct 43 ms 24180 KB Output is correct
16 Correct 58 ms 24204 KB Output is correct
17 Correct 862 ms 24180 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 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 18 ms 2792 KB Output is correct
8 Correct 45 ms 23472 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 6 ms 12532 KB Output is correct
11 Correct 45 ms 23464 KB Output is correct
12 Correct 562 ms 23824 KB Output is correct
13 Correct 55 ms 24268 KB Output is correct
14 Correct 132 ms 24176 KB Output is correct
15 Correct 43 ms 24180 KB Output is correct
16 Correct 58 ms 24204 KB Output is correct
17 Correct 862 ms 24180 KB Output is correct
18 Correct 497 ms 147016 KB Output is correct
19 Correct 21 ms 42136 KB Output is correct
20 Correct 9 ms 3288 KB Output is correct
21 Correct 539 ms 147324 KB Output is correct
22 Execution timed out 3079 ms 146248 KB Time limit exceeded
23 Halted 0 ms 0 KB -