제출 #421252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421252		SirCovidThe19th	Sateliti (COCI20_satellti)	C++14	110 / 110	899 ms	49472 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll p = 786433, q = 6291469, md = 1e9+7;

int n, m, grid[2010][2010]; ll pPow[2010], qPow[2010], hsh[2010][2010]; 
int ansR = 1, ansC = 1;

ll get(int a, int b, int x, int y){
    return (hsh[x][y] - (hsh[a-1][y]*pPow[x-a+1])%md - (hsh[x][b-1]*qPow[y-b+1])%md + (hsh[a-1][b-1]*((pPow[x-a+1]*qPow[y-b+1])%md))%md + md*2)%md;
}

int main(){
    cin >> n >> m; pPow[0] = 1; qPow[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            char x; cin >> x; int v = (x == '*') ? 1 : 2;
            grid[i][j] = v; grid[i+n][j] = v; grid[i][j+m] = v; grid[i+n][j+m] = v;
        }
    for (int i = 1; i <= n; i++) pPow[i] = (pPow[i-1]*p)%md;
    for (int i = 1; i <= m; i++) qPow[i] = (qPow[i-1]*q)%md;
    for (int i = 1; i <= n*2; i++)
        for (int j = 1; j <= m*2; j++)
            hsh[i][j] = (hsh[i-1][j]*p + hsh[i][j-1]*q - (hsh[i-1][j-1]*((p*q)%md))%md + grid[i][j] + md)%md;
    for (int i = 1; i+n-1 <= 2*n; i++)
        for (int j = 1; j+m-1 <= 2*m; j++){
            int r = 0, c = 0, high = n;
            while (r < high){
                int mid = (r+high)/2;
                if (get(ansR, ansC, ansR+mid, ansC+m-1) == get(i, j, i+mid, j+m-1)) r = mid+1;
                else high = mid;
            }high = m;
            while (c < high){
                int mid = (c+high)/2;
                if (get(ansR+r, ansC, ansR+r, ansC+mid) == get(i+r, j, i+r, j+mid)) c = mid+1;
                else high = mid;
            }
            if (grid[i+r][j+c] == 1) ansR = i, ansC = j;
        }    
    for (int i = ansR; i < ansR+n; i++){
        for (int j = ansC; j < ansC+m; j++)
            cout<<((grid[i][j] == 1) ? '*' : '.');
        cout<<endl;
    }
}

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