제출 #1183604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183604		_uros9	Sateliti (COCI20_satellti)	C++20	110 / 110	849 ms	64564 KiB

Main

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const long long longlongmax=9223372036854775807;
const int modul=998244353;
const long long mod = 1e9 + 7;


mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

const int N=1009,P1=37,P2=39;
int matr[2*N][2*N],pref[2*N][2*N],P1pw[N],P2pw[N];
int n,m;
int poww(int a,int b){
    if(b==0) return 1;
    int gg=poww(a,b>>1);
    if(b%2==1) return (((gg*gg)%mod)*a)%mod;
    return (gg*gg)%mod;
}
int sum_of_rect(int i1,int j1,int i2,int j2){
    if(i1>i2||j1>j2) return 0;
    return (pref[i2][j2]+pref[i1-1][j1-1]-pref[i1-1][j2]-pref[i2][j1-1]+5*mod)%mod;
}
int deljenje(int a,int b){
    return (a*poww(b,mod-2))%mod;
}
int hes_prvih(int d,int i,int j){///treba optimizovati
    int sum=sum_of_rect(i,j,i-1+d/m,j+m-1);
    sum+=sum_of_rect(i+d/m,j,i+d/m,j-1+d%m);
    return (sum*((P1pw[i-1]*P2pw[j-1])%mod)+10*mod)%mod;
}


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("seating.in","r",stdin);
    //freopen("seating.out","w",stdout);



    for(int i=0; i<N; i++){
        P1pw[i]=poww(poww(P1,i),mod-2);
        P2pw[i]=poww(poww(P2,i),mod-2);
    }
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;cin >> c;
            if(c=='.') matr[i][j]=matr[i+n][j]=matr[i][j+m]=matr[i+n][j+m]=2;
            else matr[i][j]=matr[i+n][j]=matr[i][j+m]=matr[i+n][j+m]=1;
        }
    }
    int p=0;
    for(int i=1; i<=2*n; i++){
        for(int j=1; j<=2*m; j++){
            pref[i][j]=(pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+poww(P1,i)*poww(P2,j)*matr[i][j]+5*mod)%mod;
        }
    }
    int I=1,J=1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int l=1,d=n*m;
            int rez=0;
            while(l<=d){
                int s=l+d>>1;
                if(hes_prvih(s,I,J)==hes_prvih(s,i,j)){
                    rez=s;
                    l=s+1;
                }
                else
                    d=s-1;
            }

            if(matr[I+rez/m][J+rez%m]>matr[i+rez/m][j+rez%m]){I=i;J=j;}
        }
    }


    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++)
            cout << (matr[I+i][J+j]==1?'*':'.');
        cout << endl;
    }



    return 0;
}
/*
    abcde
    01234
    04321 --> 12340
              0   1
    011
    110

1
3 1
1 2 3
3 5

*/

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60