oj.uz

Submission #1103092

# Submission time Handle Problem Language Result Execution time Memory
1103092 2024-10-20T00:36:02 Z orcslop Sateliti (COCI20_satellti) C++17
10 / 110
 45 ms 17000 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4600 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 3 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4600 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 3 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 45 ms 17000 KB Output is correct
9 Correct 3 ms 4688 KB Output is correct
10 Incorrect 3 ms 16768 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4600 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 3 ms 4432 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 45 ms 17000 KB Output is correct
9 Correct 3 ms 4688 KB Output is correct
10 Incorrect 3 ms 16768 KB Output isn't correct
11 Halted 0 ms 0 KB -