제출 #573415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573415		pokmui9909	Sateliti (COCI20_satellti)	C++17	110 / 110	451 ms	65100 KiB

Main

#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';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60