oj.uz

Submission #705037

# Submission time Handle Problem Language Result Execution time Memory
705037 2023-03-03T08:58:49 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 2 ms 1876 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 3 ms 1748 KB Output is correct
4 Correct 64 ms 1784 KB Output is correct
5 Correct 2 ms 1832 KB Output is correct
6 Correct 2 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 2 ms 1876 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 3 ms 1748 KB Output is correct
4 Correct 64 ms 1784 KB Output is correct
5 Correct 2 ms 1832 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 70 ms 1888 KB Output is correct
8 Correct 62 ms 16004 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 72 ms 15992 KB Output is correct
12 Correct 2082 ms 16220 KB Output is correct
13 Correct 117 ms 16520 KB Output is correct
14 Correct 408 ms 16516 KB Output is correct
15 Correct 62 ms 16588 KB Output is correct
16 Correct 123 ms 16548 KB Output is correct
17 Execution timed out 3067 ms 16496 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 3 ms 1748 KB Output is correct
4 Correct 64 ms 1784 KB Output is correct
5 Correct 2 ms 1832 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 70 ms 1888 KB Output is correct
8 Correct 62 ms 16004 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 72 ms 15992 KB Output is correct
12 Correct 2082 ms 16220 KB Output is correct
13 Correct 117 ms 16520 KB Output is correct
14 Correct 408 ms 16516 KB Output is correct
15 Correct 62 ms 16588 KB Output is correct
16 Correct 123 ms 16548 KB Output is correct
17 Execution timed out 3067 ms 16496 KB Time limit exceeded
18 Halted 0 ms 0 KB -