Submission #1209285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209285		sofija6	Sateliti (COCI20_satellti)	C++20	110 / 110	257 ms	68516 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define MAXN 1010
#define MOD 1000000009
using namespace std;
ll a[2*MAXN][2*MAXN],pref[2*MAXN][2*MAXN],p=5,q=11,degp[2*MAXN],degq[2*MAXN];
char c[2*MAXN][2*MAXN];
void Init()
{
    degp[0]=degq[0]=1;
    for (ll i=1; i<2*MAXN; i++)
    {
        degp[i]=(degp[i-1]*p)%MOD;
        degq[i]=(degq[i-1]*q)%MOD;
    }
}
ll Calc(ll i1,ll j1,ll i2,ll j2)
{
    return (pref[i2][j2]-pref[i1-1][j2]-pref[i2][j1-1]+pref[i1-1][j1-1]+2*MOD)%MOD;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,m;
    cin >> n >> m;
    Init();
    for (ll i=1; i<=n; i++)
    {
        for (ll j=1; j<=m; j++)
        {
            cin >> c[i][j];
            a[i][j]=c[i][j]=='.'?2 : 1;
            a[i+n][j]=a[i+n][j+m]=a[i][j+m]=a[i][j];
            c[i+n][j]=c[i+n][j+m]=c[i][j+m]=c[i][j];
        }
    }
    for (ll i=1; i<=2*n; i++)
    {
        for (ll j=1; j<=2*m; j++)
            pref[i][j]=(pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(a[i][j]*(degp[i]*degq[j])%MOD)%MOD+MOD)%MOD;
    }
    ll ansi=1,ansj=1;
    for (ll i=1; i<=n+1; i++)
    {
        for (ll j=1; j<=m+1; j++)
        {
            ll l=1,r=n,mid,indi=n+1,indj=0;
            ll val0=(degp[max(ansi,i)-ansi]*degq[max(ansj,j)-ansj])%MOD,val1=(degp[max(ansi,i)-i]*degq[max(ansj,j)-j])%MOD;
            while (l<=r)
            {
                mid=(l+r)/2;
                if ((val0*Calc(ansi,ansj,ansi+mid-1,ansj+m-1))%MOD==(val1*Calc(i,j,i+mid-1,j+m-1))%MOD)
                    l=mid+1;
                else
                {
                    indi=mid;
                    r=mid-1;
                }
            }
            if (indi==n+1)
                continue;
            l=1;
            r=m;
            while (l<=r)
            {
                mid=(l+r)/2;
                if ((val0*Calc(ansi+indi-1,ansj,ansi+indi-1,ansj+mid-1))%MOD==(val1*Calc(i+indi-1,j,i+indi-1,j+mid-1))%MOD)
                    l=mid+1;
                else
                {
                    indj=mid;
                    r=mid-1;
                }
            }
            if (c[i+indi-1][j+indj-1]<c[ansi+indi-1][ansj+indj-1])
            {
                ansi=i;
                ansj=j;
            }
        }
    }
    for (ll i=ansi; i<ansi+n; i++)
    {
        for (ll j=ansj; j<ansj+m; j++)
            cout << c[i][j];
        cout << "\n";
    }
    return 0;
}

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