oj.uz

Submission #705036

# Submission time Handle Problem Language Result Execution time Memory
705036 2023-03-03T08:57:30 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
10 / 110
 3000 ms 16588 KB 
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
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 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 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);
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 1876 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 64 ms 1780 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 70 ms 1888 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1876 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 64 ms 1780 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 70 ms 1888 KB Output is correct
8 Correct 66 ms 16076 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 78 ms 15992 KB Output is correct
12 Correct 2094 ms 16216 KB Output is correct
13 Correct 120 ms 16588 KB Output is correct
14 Correct 406 ms 16512 KB Output is correct
15 Correct 65 ms 16588 KB Output is correct
16 Correct 125 ms 16512 KB Output is correct
17 Execution timed out 3063 ms 16484 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1876 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 64 ms 1780 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 70 ms 1888 KB Output is correct
8 Correct 66 ms 16076 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 78 ms 15992 KB Output is correct
12 Correct 2094 ms 16216 KB Output is correct
13 Correct 120 ms 16588 KB Output is correct
14 Correct 406 ms 16512 KB Output is correct
15 Correct 65 ms 16588 KB Output is correct
16 Correct 125 ms 16512 KB Output is correct
17 Execution timed out 3063 ms 16484 KB Time limit exceeded
18 Halted 0 ms 0 KB -