제출 #533811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533811		maximath_1	Sateliti (COCI20_satellti)	C++11	110 / 110	491 ms	74220 KiB

Main

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

#define ll long long
const int MX = 2005;
const ll mod = 420691273;

int n, m;
string G[MX]; int grd[MX][MX];
ll p[MX][MX], pref[MX][MX]; // 2d hashing

ll query(int x, int y, int sx, int sy){
	ll get = pref[x + sx][y + sy] + pref[x][y];
	(get += (mod - pref[x + sx][y]) + (mod - pref[x][y + sy])) %= mod;
	if(get < 0) get += mod;
	return get;
}

bool check_eq(int ax, int ay, int bx, int by, int sx, int sy){
	ll geta = (query(ax, ay, sx, sy) * 1ll * p[bx][by]) % mod;
	ll getb = (query(bx, by, sx, sy) * 1ll * p[ax][ay]) % mod;
	if(geta < 0) geta += mod;
	if(getb < 0) getb += mod;
	if(geta == getb) return true;
	return false;
}

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

	cin >> n >> m;
	for(int i = 0; i < n; i ++){
		cin >> G[i];
		for(int j = 0; j < m; j ++)
			grd[i][j] = (G[i][j] == '*' ? 1 : 0);
	}

	for(int i = 0; i < MX; i ++){
		for(int j = 0; j < MX; j ++){
			if(i == 0){
				if(j == 0) p[i][j] = 1ll;
				else p[i][j] = (p[i][j - 1] * 3ll) % mod;
			}else p[i][j] = (p[i - 1][j] * 2ll) % mod;
			if(p[i][j] < 0) p[i][j] += mod;
		}
	}

	for(int i = 0; i < 2 * n; i ++)
		for(int j = 0; j < 2 * m; j ++){
			pref[i + 1][j + 1] = ((grd[i % n][j % m] * 1ll * p[i][j]) % mod 
				+ pref[i + 1][j] + pref[i][j + 1] + mod - pref[i][j]) % mod;
			if(pref[i + 1][j + 1] < 0) pref[i + 1][j + 1] += mod;
		}

	int ansx = 0, ansy = 0;

	for(int x = 0; x < n; x ++){
		for(int y = 0; y < m; y ++){
			int lf = 0, rg = n - 1, dx = 0;
			for(int md; lf <= rg;){
				md = (lf + rg) / 2;
				if(check_eq(ansx, ansy, x, y, md, m)){
					dx = md;
					lf = md + 1;
				}else rg = md - 1;
			}
			lf = 0, rg = m - 1; int dy = 0;
			for(int md; lf <= rg;){
				md = (lf + rg) / 2;
				if(check_eq(ansx + dx, ansy, x + dx, y, 1, md)){
					dy = md; lf = md + 1;
				}else rg = md - 1;
			}

			if(G[(x + dx) % n][(y + dy) % m] == '*' && G[(ansx + dx) % n][(ansy + dy) % m] == '.'){
				ansx = x; ansy = y;
			}
		}
	}

	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++)
			cout << G[(ansx + i) % n][(ansy + j) % m];
		cout << endl;
	}
}

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