oj.uz

Submission #705035

# Submission time Handle Problem Language Result Execution time Memory
705035 2023-03-03T08:56:47 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
10 / 110
 3000 ms 16596 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>>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 4 ms 1876 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 2 ms 1784 KB Output is correct
4 Correct 63 ms 1768 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 1876 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 2 ms 1784 KB Output is correct
4 Correct 63 ms 1768 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 1876 KB Output is correct
8 Correct 70 ms 16060 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 76 ms 16068 KB Output is correct
12 Correct 2109 ms 16284 KB Output is correct
13 Correct 121 ms 16596 KB Output is correct
14 Correct 405 ms 16596 KB Output is correct
15 Correct 69 ms 16596 KB Output is correct
16 Correct 124 ms 16584 KB Output is correct
17 Execution timed out 3077 ms 16512 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 2 ms 1784 KB Output is correct
4 Correct 63 ms 1768 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 1876 KB Output is correct
8 Correct 70 ms 16060 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 76 ms 16068 KB Output is correct
12 Correct 2109 ms 16284 KB Output is correct
13 Correct 121 ms 16596 KB Output is correct
14 Correct 405 ms 16596 KB Output is correct
15 Correct 69 ms 16596 KB Output is correct
16 Correct 124 ms 16584 KB Output is correct
17 Execution timed out 3077 ms 16512 KB Time limit exceeded
18 Halted 0 ms 0 KB -