Submission #1150706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150706		akzytr	Sateliti (COCI20_satellti)	C++20	110 / 110	621 ms	64880 KiB

Main

#include <bits/stdc++.h>
#define ve vector
#define ar array 
#define pb push_back
#define ins insert

#define endl '\n'
#define ll long long
using namespace std;


const int MXN = 2000;
const ll P = 2;
const ll Q = 3;
const ll B = 1e9+7;

ll p[MXN][MXN];
ll s[MXN][MXN];
int n, m;

void po(){
    for(int i = 0; i < 2 * n; i++){
        for(int j = 0; j < 2 * m; j++){
            if(i == 0 && j == 0){
                p[i][j] = 1;
            }
            else if(i == 0){
                p[i][j] = (p[i][j-1] * Q)%B;
            }
            else{
                p[i][j] = (p[i-1][j] * P)%B;
            }

            
            s[i][j] *= p[i][j];
            if(i > 0){
                s[i][j] += s[i-1][j];
                s[i][j]%=B;
            }
            if(j > 0){
                s[i][j] += s[i][j-1];
                s[i][j]%=B;
            }
            if(i > 0 && j > 0){
                s[i][j] -= s[i-1][j-1];
                s[i][j]%=B;
                if(s[i][j]< 0){
                    s[i][j]+=B;
                }
            }
        }
    }
}

ll calc(int x1, int y1, int x2, int y2){
    assert(x1 <= x2 && y1 <= y2);

    ll sy = s[x2][y2];
    if(y1 > 0){
        sy = ((sy - s[x2][y1-1])%B + B)%B;
    }
    if(x1 > 0){
        sy = ((sy - s[x1-1][y2])%B + B)%B;
    }
    if(x1 > 0 && y1 > 0){
        sy = sy + s[x1-1][y1-1];
        sy%=B;
    }
    return sy;
}

int main(){
    cin >> n >> m;

    char cpy[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char x;
            cin >> x;
            cpy[i][j] = x;
            s[i][j] = s[i+n][j] = s[i+n][j+m] = s[i][j+m] = (x=='.');
        }
    }
    po();
    
    
    int x1 = 0;
    int x2 = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int l = 0;
            int r = n-1;
            while(l < r){
                int mi = (l + r)/2;
                ll a1 = calc(x1, x2, x1 + mi, x2+m-1) * p[i][j];
                a1%=B;
                ll a2 = calc(i, j, i+ mi, j+m-1) * p[x1][x2];
                a2%=B;
                if(a1 != a2){
                    r = mi;
                }
                else{
                    l = mi+1;
                }
            }

            int li = 0;
            int ri = m-1;

            while(li < ri){
                int mi = (li + ri)/2;
                ll a1 = calc(x1+r, x2, x1+r, x2+mi) * p[i+r][j];
                ll a2 = calc(i+r, j, i+r, j+mi) * p[x1+r][x2];
                a1%=B;
                a2%=B;

                if(a1 != a2){
                    ri = mi;
                }
                else{
                    li = mi+1;
                }
            }

            // cout << "compare " << x1 <<" " << x2 << " " << i << " " << j << " diff at " << r << " " << ri << " " << calc(x1+r, x2+ri, x1+r, x2+ri) << endl;
            if(calc(x1+r, x2+ri, x1+r, x2+ri) != 0){
                x1 = i;
                x2 = j;
            }
        }
    }
    
    for(int i = x1; i < n; i++){
        for(int j = x2; j < m; j++){
            cout << cpy[i][j];
        }
        for(int j = 0; j < x2; j++){
            cout << cpy[i][j];
        }
        cout << endl;
    }

    for(int i = 0; i < x1; i++){
        for(int j = x2; j < m; j++){
            cout << cpy[i][j];
        }
        for(int j = 0; j < x2; j++){
            cout << cpy[i][j];
        }
        cout << endl;
    }
}

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