Submission #533846

#	Time	Username	Problem	Language	Result	Execution time	Memory
533846		MetalPower	Sateliti (COCI20_satellti)	C++14	0 / 110	11 ms	1868 KiB

Main

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

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e3 + 100;
const int MOD = 1e9 + 7;

int N, M, arr[MX][MX];
int pref[MX][MX], h[MX][MX], x[MX][MX];

int add(int a, int b){
	a += b;
	if(a < 0) a += MOD;
	if(a >= MOD) a -= MOD;
	return a;
}

int que(int a, int b, int c, int d){
	int ans = pref[c][d];
	if(a > 0) ans = add(ans, -pref[a - 1][d]);
	if(b > 0) ans = add(ans, -pref[c][b - 1]);
	if(a > 0 && b > 0) ans = add(ans, pref[a - 1][b - 1]);
	return ans;
}

int inv(int a){
	int r = 1, b = MOD - 2;
	while(b){
		if(b & 1) r = 1ll * r * a % MOD;
		a = 1ll * a * a % MOD;
		b >>= 1;
	}
	return r;
}

int off(int fi, int fj, int si, int sj, int di, int dj){
	int _i = ((si + di) % N < (fi + di) % N) ? 0 : fi + di;
	int _j = ((sj + dj) % N < (fj + dj) % N) ? 0 : fj + dj;
	return 1ll * que(fi + di, fj + dj, si + di, sj + dj) * inv(x[_i][_j]) % MOD;
}

bool cmp(int ai, int aj, int bi, int bj){

	int v = -1;
	{
		int l = 0, r = N - 1;

		while(l <= r){
			int mid = l + r >> 1;
			if(off(0, 0, mid, M - 1, ai, aj) == off(0, 0, mid, M - 1, bi, bj)){
				l = mid + 1; v = mid;
			}else{
				r = mid - 1;
			}
		}

		v++;
	}

	int h = -1;
	{
		int l = 0, r = M - 1, memo = -1;

		while(l <= r){
			int mid = l + r >> 1;
			if(off(0, 0, v, mid, ai, aj) == off(0, 0, v, mid, bi, bj)){
				l = mid + 1; h = mid;
			}else{
				r = mid - 1;
			}
		}

		h++;
	}

	if(arr[(v + ai) % N][(h + aj) % M] > arr[(v + bi) % N][(h + bj) % M]) return true;
	else return false;
}

char tmp[MX][MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M;

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			char c; cin >> c; tmp[i][j] = c;
			arr[i][j] = (c == '*');
		}
	}

	int curr = 1;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			x[i][j] = curr;
			h[i][j] = arr[i][j] * curr;

			{
				pref[i][j] = h[i][j];
				if(i > 0) pref[i][j] = add(pref[i][j], pref[i - 1][j]);
				if(j > 0) pref[i][j] = add(pref[i][j], pref[i][j - 1]);
				if(i > 0 && j > 0) pref[i][j] = add(pref[i][j], -pref[i - 1][j - 1]);
			}

			if(j == M - 1) curr = 1ll * curr * 3 % MOD;
			else curr = 1ll * curr * 2 % MOD;
		}
	}

	for(int i = 0; i < 2 * N; i++){
		for(int j = 0; j < 2 * M; j++){
			x[i][j] = x[i % N][j % M];
			h[i][j] = h[i % N][j % M];
			
			{
				pref[i][j] = h[i][j];
				if(i > 0) pref[i][j] = add(pref[i][j], pref[i - 1][j]);
				if(j > 0) pref[i][j] = add(pref[i][j], pref[i][j - 1]);
				if(i > 0 && j > 0) pref[i][j] = add(pref[i][j], -pref[i - 1][j - 1]);
			}
		}
	}

	int _i = 0, _j = 0;

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(cmp(i, j, _i, _j)) _i = i, _j = j;
		}
	}

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cout << tmp[(i + _i) % N][(j + _j) % M];
		}
		cout << '\n';
	}
}

Compilation message (stderr)

Main.cpp: In function 'bool cmp(int, int, int, int)':
Main.cpp:53:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |    int mid = l + r >> 1;
      |              ~~^~~
Main.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |    int mid = l + r >> 1;
      |              ~~^~~
Main.cpp:66:25: warning: unused variable 'memo' [-Wunused-variable]
   66 |   int l = 0, r = M - 1, memo = -1;
      |                         ^~~~

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