제출 #1219390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219390		rcll	Sateliti (COCI20_satellti)	C++20	110 / 110	392 ms	75888 KiB

Main

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

const int N=2e3+5,MOD=998244353,p=11,q=17;
int grid[N][N],pp[N],qp[N],h[N][N],sum[N][N];

int n,m;
int ansx,ansy;

void precompute() {
    pp[0]=1;
    qp[0]=1;
    for(int i=1;i < N;i++){
        pp[i]=pp[i-1]*p%MOD;
        qp[i]=qp[i-1]*q%MOD;
    }
    for (int i=0; i<2*n; i++) {
        for (int j=0; j<2*m; j++) {
            h[i][j]=grid[i%n][j%m]*pp[i]%MOD*qp[j]%MOD;
        }
    }
    for (int i=0; i<2*n; i++) {
        for (int j=0; j<2*m; j++) {
            sum[i+1][j+1]=(h[i][j]+sum[i+1][j]+sum[i][j+1]-sum[i][j]);
        }
    }
}

bool check(int x1,int y1,int x2,int y2,int dx,int dy){
    return (((sum[x1+dx][y1+dy]-sum[x1+dx][y1]-sum[x1][y1+dy]+sum[x1][y1])%MOD+MOD)%MOD*pp[x2]%MOD*qp[y2]%MOD==((sum[x2+dx][y2+dy]-sum[x2+dx][y2]-sum[x2][y2+dy]+sum[x2][y2])%MOD+MOD)%MOD*pp[x1]%MOD*qp[y1]%MOD);
}

signed main() {
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            char c;
            cin >> c;
            if (c=='.') {
                grid[i][j]=1;
            }
        }
    }
    precompute();
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            int l=0,r=n;
            while (l+1<r) {
                int mid=l+r>>1;
                if (check(i,j,ansx,ansy,mid,m)) {
                    l=mid;
                } else {
                    r=mid;
                }
            }
            int dx=l;
            l=0,r=m;
            while (l+1<r) {
                int mid=l+r>>1;
                if (check(i+dx,j,ansx+dx,ansy,1,mid)) {
                    l=mid;
                } else {
                    r=mid;
                }
            }
            int dy=l;
            if (grid[(i+dx)%n][(j+dy)%m]<=grid[(ansx+dx)%n][(ansy+dy)%m]) {
                ansx=i;
                ansy=j;
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cout << (grid[(ansx+i)%n][(ansy+j)%m] ? '.' : '*');
        }
        cout << '\n';
    }
}

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