Submission #483314

#	Time	Username	Problem	Language	Result	Execution time	Memory
483314		rainboy	Sateliti (COCI20_satellti)	C11	110 / 110	1345 ms	74632 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	1000
#define M	1000
#define MD	0x7fffffff

int max(int a, int b) { return a > b ? a : b; }

int X = 12345, Y = 54321;

int ppx[N * M * 2 + 1], ppy[N * M * 2 + 1], n, m;

void init() {
	int i;

	ppx[0] = ppy[0] = 1;
	for (i = 1; i <= N * M * 2; i++) {
		ppx[i] = (long long) ppx[i - 1] * X % MD;
		ppy[i] = (long long) ppy[i - 1] * Y % MD;
	}
}

int hash1(int *xx, int *pp, int l, int r, int c) {
	if (l > r)
		return 0;
	else {
		int x = (xx[r] - (l == 0 ? 0 : (long long) xx[l - 1] * pp[(r - l + 1) * c])) % MD;

		if (x < 0)
			x += MD;
		return x;
	}
}

int xx[N][M * 2], yy[N][M * 2], xx_[M][N * 2], yy_[M][N * 2];

long long hash2(int i, int j, int len) {
	int q = len / m, r = len % m, x, y;

	x = ((long long) hash1(xx_[j], ppx, i, i + q - 1, m) + hash1(xx[(i + q) % n], ppx, j, j + r - 1, 1)) % MD;
	y = ((long long) hash1(yy_[j], ppy, i, i + q - 1, m) + hash1(yy[(i + q) % n], ppy, j, j + r - 1, 1)) % MD;
	return (long long) x * MD + y;
}

int main() {
	static char cc[N][M + 1], cc_[N][M + 1];
	static int aa[N][M * 2], aax[M][N * 2], aay[M][N * 2];
	int i, i_, j, j_;

	init();
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%s", cc[i]);
		for (j = 0; j < m; j++)
			aa[i][j] = aa[i][m + j] = cc[i][j] == '*' ? 0 : 1;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m * 2; j++) {
			xx[i][j] = ((long long) (j == 0 ? 0 : xx[i][j - 1]) * X + aa[i][j % m]) % MD;
			yy[i][j] = ((long long) (j == 0 ? 0 : yy[i][j - 1]) * Y + aa[i][j % m]) % MD;
		}
		for (j = 0; j < m; j++)
			aax[j][i] = aay[j][n + i] = hash1(xx[i], ppx, j, j + m - 1, 1);
	}
	for (j = 0; j < m; j++)
		for (i = 0; i < n * 2; i++) {
			xx_[j][i] = ((long long) (i == 0 ? 0 : xx_[j][i - 1]) * ppx[m] + aax[j][i % n]) % MD;
			yy_[j][i] = ((long long) (i == 0 ? 0 : yy_[j][i - 1]) * ppy[m] + aay[j][i % n]) % MD;
		}
	i_ = 0, j_ = 0;
	for (i = 0; i < n; i++)
		for (j = i == 0 ? 1 : 0; j < m; j++) {
			int lower = -1, upper = n * m, q, r;

			while (upper - lower > 1) {
				int len = (lower + upper) / 2;

				if (hash2(i_, j_, len) != hash2(i, j, len))
					upper = len;
				else
					lower = len;
			}
			q = lower / m, r = lower % m;
			if (aa[(i_ + q) % n][(j_ + r) % m] > aa[(i + q) % n][(j + r) % m])
				i_ = i, j_ = j;
		}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			cc_[i][j] = cc[(i_ + i) % n][(j_ + j) % m];
	for (i = 0; i < n; i++)
		printf("%s\n", cc_[i]);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:54:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

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