제출 #373352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373352		sam571128	Sateliti (COCI20_satellti)	C++14	110 / 110	686 ms	77164 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

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(){
	fastio
	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";
	}
}

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

Main.cpp: In function 'int main()':
Main.cpp:53:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = l+r>>1;
      |               ~^~
Main.cpp:60:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = l+r>>1;
      |               ~^~

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