oj.uz

Submission #573415

# Submission time Handle Problem Language Result Execution time Memory
573415 2022-06-06T15:06:59 Z pokmui9909 Sateliti (COCI20_satellti) C++17
110 / 110
 451 ms 65100 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll P = 197, Q = 971, MOD = 998244353;
ll N, M;
ll A[2005][2005];
ll Hash[2005][2005];
ll Pm[2005], Qm[2005];
ll Pim[2005], Qim[2005];
ll Pow(ll A, ll B){
    if(B == 0) return 1;
    if(B % 2 == 1) return A * Pow(A, B - 1) % MOD;
    ll k = Pow(A, B / 2); return k * k % MOD;
}
ll Inv(ll A){
    return Pow(A, MOD - 2);
}
ll GetHash(ll x1, ll x2, ll y1, ll y2){
    ll K = (Hash[x2][y2] - Hash[x1 - 1][y2] - Hash[x2][y1 - 1] + Hash[x1 - 1][y1 - 1]) % MOD;
    K *= Pim[x1] * Qim[y1] % MOD; K %= MOD;
    return (K + MOD) % MOD;
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> M;
    for(ll i = 1; i <= N; i++){
        for(ll j = 1; j <= M; j++){
            char c; cin >> c;
            if(c == '*') A[i][j] = 0;
            else A[i][j] = 1;
            A[i + N][j] = A[i][j + M] = A[i + N][j + M] = A[i][j];
        }
    }
    for(ll i = 0; i < 2005; i++){
        Pm[i] = Pow(P, i), Pim[i] = Inv(Pm[i]);
        Qm[i] = Pow(Q, i), Qim[i] = Inv(Qm[i]);
    }
    for(ll i = 1; i <= 2 * N; i++){
        for(ll j = 1; j <= 2 * M; j++){
            Hash[i][j] = Hash[i - 1][j] + Hash[i][j - 1] - Hash[i - 1][j - 1] + (A[i][j] + 123) * Pm[i] % MOD * Qm[j] % MOD;
            Hash[i][j] %= MOD;
        }
    }
    ll x = 1, y = 1;
    for(ll i = 1; i <= N; i++){
        for(ll j = 1; j <= M; j++){
            if(i == 1 && j == 1) continue;
            ll L = 1, R = N;
            while(L <= R){
                ll m = (L + R) / 2;
                if(GetHash(x, x + m - 1, y, y + M - 1) != GetHash(i, i + m - 1, j, j + M - 1)) R = m - 1;
                else L = m + 1;
            }
            ll dx = L;
            L = 1, R = M;
            while(L <= R){
                ll m = (L + R) / 2;
                if(GetHash(x + dx - 1, x + dx - 1, y, y + m - 1) != GetHash(i + dx - 1, i + dx - 1, j, j + m - 1)) R = m - 1;
                else L = m + 1;
            }
            ll dy = L;
            if(A[x + dx - 1][y + dy - 1] > A[i + dx - 1][j + dy - 1]){
                x = i, y = j;
            }
        }
    }
    for(ll i = 1; i <= N; i++){
        for(ll j = 1; j <= M; j++){
            ll p = x + i - 1, q = y + j - 1;
            if(p > N) p -= N; if(q > M) q -= M;
            cout << (A[p][q] == 0 ? '*' : '.');
        }
        cout << '\n';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:73:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   73 |             if(p > N) p -= N; if(q > M) q -= M;
      |             ^~
Main.cpp:73:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   73 |             if(p > N) p -= N; if(q > M) q -= M;
      |                               ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 3 ms 1248 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 3 ms 1220 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 3 ms 1248 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 3 ms 1220 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 35 ms 10580 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 34 ms 10580 KB Output is correct
12 Correct 38 ms 10744 KB Output is correct
13 Correct 35 ms 10932 KB Output is correct
14 Correct 40 ms 10944 KB Output is correct
15 Correct 34 ms 10916 KB Output is correct
16 Correct 39 ms 10920 KB Output is correct
17 Correct 39 ms 10928 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 3 ms 1248 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 3 ms 1220 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 35 ms 10580 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 34 ms 10580 KB Output is correct
12 Correct 38 ms 10744 KB Output is correct
13 Correct 35 ms 10932 KB Output is correct
14 Correct 40 ms 10944 KB Output is correct
15 Correct 34 ms 10916 KB Output is correct
16 Correct 39 ms 10920 KB Output is correct
17 Correct 39 ms 10928 KB Output is correct
18 Correct 409 ms 64972 KB Output is correct
19 Correct 13 ms 17236 KB Output is correct
20 Correct 8 ms 1620 KB Output is correct
21 Correct 373 ms 65092 KB Output is correct
22 Correct 441 ms 65032 KB Output is correct
23 Correct 390 ms 65084 KB Output is correct
24 Correct 440 ms 65052 KB Output is correct
25 Correct 375 ms 65028 KB Output is correct
26 Correct 438 ms 65100 KB Output is correct
27 Correct 451 ms 65060 KB Output is correct