oj.uz

Submission #705038

# Submission time Handle Problem Language Result Execution time Memory
705038 2023-03-03T08:59:14 Z 1075508020060209tc Sateliti (COCI20_satellti) C++14
50 / 110
 3000 ms 100900 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 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 2 ms 1748 KB Output is correct
4 Correct 17 ms 1804 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 19 ms 1900 KB Output is correct

Subtask #2
40.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 2 ms 1748 KB Output is correct
4 Correct 17 ms 1804 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 19 ms 1900 KB Output is correct
8 Correct 33 ms 16020 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 40 ms 16016 KB Output is correct
12 Correct 562 ms 16232 KB Output is correct
13 Correct 45 ms 16536 KB Output is correct
14 Correct 130 ms 16544 KB Output is correct
15 Correct 34 ms 16548 KB Output is correct
16 Correct 51 ms 16536 KB Output is correct
17 Correct 849 ms 16536 KB Output is correct

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 2 ms 1748 KB Output is correct
4 Correct 17 ms 1804 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 19 ms 1900 KB Output is correct
8 Correct 33 ms 16020 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 40 ms 16016 KB Output is correct
12 Correct 562 ms 16232 KB Output is correct
13 Correct 45 ms 16536 KB Output is correct
14 Correct 130 ms 16544 KB Output is correct
15 Correct 34 ms 16548 KB Output is correct
16 Correct 51 ms 16536 KB Output is correct
17 Correct 849 ms 16536 KB Output is correct
18 Correct 395 ms 100744 KB Output is correct
19 Correct 16 ms 25684 KB Output is correct
20 Correct 7 ms 2368 KB Output is correct
21 Correct 430 ms 100900 KB Output is correct
22 Execution timed out 3030 ms 99780 KB Time limit exceeded
23 Halted 0 ms 0 KB -