Submission #1103092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103092		orcslop	Sateliti (COCI20_satellti)	C++17	10 / 110	45 ms	17000 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define f first
#define s second
 
const int N = 2005; 
const int MOD = 1e9 + 7; 
 
ll exp(ll base, ll exp){
    ll ret = 1; 
    while(exp){
        if(exp & 1) ret = ret * base % MOD; 
        base = base * base % MOD; 
        exp >>= 1; 
    }
    return ret; 
}
 
int n, m; 
int v[N][N]; 
ll ps[N][N]; 
ll p5[N], p3[N]; 
ll i5[N], i3[N]; 
 
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    p5[0] = p3[0] = 1; 
    for(int i = 1; i < N; i++){
        p5[i] = p5[i - 1] * 478427 % MOD; 
        p3[i] = p3[i - 1] * 561713 % MOD; 
        i5[i] = exp(p5[i], MOD - 2); 
        i3[i] = exp(p3[i], MOD - 2); 
    }
    cin >> n >> m; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char c; 
            cin >> c; 
            ll val = (c == '.' ? 123731 : 72031); 
            v[i][j] = v[i + n][j] = v[i][j + m] = v[i + n][j + m] = (c == '.'); 
            ps[i][j] = ps[i + n][j] = ps[i][j + m] = ps[i + n][j + m] = val; 
        }
    }
    for(int i = 1; i <= 2 * n; i++){
        for(int j = 1; j <= 2 * m; j++){
            ps[i][j] *= p5[i] * p3[j] % MOD; 
            ps[i][j] %= MOD; 
        }
    }
    for(int i = 1; i <= 2 * n; i++){
        for(int j = 1; j <= 2 * m; j++){
            ps[i][j] += ps[i - 1][j]; 
            ps[i][j] += ps[i][j - 1]; 
            ps[i][j] -= ps[i - 1][j - 1]; 
            ps[i][j] = (ps[i][j] % MOD + MOD) % MOD; 
        }
    }
    auto rect = [&](int a, int b, int c, int d) -> ll {
        if(a > c || b > d) return 0; 
        return ((ps[c][d] - ps[c][b - 1] - ps[a - 1][d] + ps[a - 1][b - 1]) % MOD + MOD) % MOD; 
    }; 
    auto get_hash = [&](int x, int y, int d) -> ll {
        ll ret = rect(x, y, x + d / m - 1, y + n - 1); 
        ret += rect(x + d / m, y, x + d / m, y + d % m - 1); 
        ret = ret % MOD * i5[x] % MOD * i3[y] % MOD; 
        return ret; 
    }; 
    auto nxt = [&](int a, int b, int d) -> int {
        a += d / m; 
        b += d % m; 
        return v[a][b]; 
    }; 
    pair<int, int> best = {1, 1}; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == j && i == 1) continue; 
            int low = 0, high = n * m; 
            while (low < high) {
                int mid = low + (high - low + 1) / 2;
                if (get_hash(best.f, best.s, mid) == get_hash(i, j, mid)) low = mid; 
                else high = mid - 1;
            }
            if(nxt(i, j, low) < nxt(best.f, best.s, low)){
                best = {i, j}; 
            }
        }
    }   
    for(int i = best.f; i < best.f + n; i++){
        for(int j = best.s; j < best.s + m; j++){
            cout << (v[i][j] ? '.' : '*'); 
        }
        cout << '\n'; 
    }
    return 0; 
}

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