Submission #1294551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294551		behesht	Sateliti (COCI20_satellti)	C++20	10 / 110	553 ms	38032 KiB

Main

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e9 + (35 / 10); // 35 ---> 36
const int MAXN = 2e3 + (35 / 10); // 35 ---> 36
const int MOD = 1e9 + 7;

int n, m;
int p = 73;
int pw[MAXN * MAXN];
bool a[MAXN][MAXN];
int h[MAXN][MAXN];

int Pw(int a, int b){
    
    if(!b)
        return 1;

    int res = Pw(a, b / 2);
    res = (res * res) % MOD;

    if(b & 1)
        res = (res * a) % MOD;

    return res;
}

int Hash(int i, int j, int ni, int nj){
    int res = (((h[ni][nj] - h[i - 1][nj] - h[ni][j - 1] + h[i - 1][j - 1]) % MOD) + MOD) % MOD;
    res *= Pw(pw[m * (i - 1) + j], MOD - 2);
    res %= MOD;

    // d4(i, j, ni, nj);
    // d1(res);
    // cout << endl;
    return res;
}

bool check(int i, int j, int ni, int nj){
    
    if(Hash(i, j, i + n - 1, j + m - 1) == Hash(ni, nj, ni + n - 1, nj + m - 1))
        return 0;
    
    int l = 0, r = n + 1, mid;

    while(r - l > 1){
        mid = (r + l) >> 1;

        if(Hash(i, j, i + mid, j + m - 1) == Hash(ni, nj, ni + mid, nj + m - 1))
            l = mid;
        
        else 
            r = mid;
    }

    int x = l;
    // d1(x);
    
    l = 0, r = m + 1;

    while(r - l > 1){
        mid = (r + l) >> 1;
        // d1(mid);
        if(Hash(i + x, j, i + x, j + mid - 1) == Hash(ni + x, nj, ni + x, nj + mid - 1))
            l = mid;

        else 
            r = mid;
    }
    // d1(l);
    if(a[i + x][j + l] < a[ni + x][nj + l]){
        // d4(i, j, ni, nj);
        return 1;
    }

    else 
        return 0;
}

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

    pw[0] = 1;

    for(int i = 1; i < MAXN * MAXN; i++)
        pw[i] = (pw[i - 1] * p) % MOD;

    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char c;
            cin >> c;

            a[i][j] = (c == '*');
            a[i + n][j] = a[i][j];
            a[i][j + m] = a[i][j];
            a[i + n][j + m] = a[i][j];
        }
    }

    for(int i = 1; i <= 2 * n; i++){
        for(int j = 1; j <= 2 * m; j++){
            h[i][j] = h[i - 1][j] + h[i][j - 1] - h[i - 1][j - 1];
            h[i][j] %= MOD;
            h[i][j] += (a[i][j] + 1) * pw[(i - 1) * m + j];
            h[i][j] %= MOD;
            h[i][j] += MOD;
            h[i][j] %= MOD;
        }
    }

    arr(2) ans = {1, 1};

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(check(ans[0], ans[1], i, j))
                ans = {i, j};
            
            // d2(i, j);
        }
    }

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

        cout << endl;
    }
}

// Ey To Bahane! :_)))

// -------------<3------------- //
/*
Magasan dor shirini: 

1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 

*/

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