oj.uz

Submission #483314

# Submission time Handle Problem Language Result Execution time Memory
483314 2021-10-28T16:01:20 Z rainboy Sateliti (COCI20_satellti) C
110 / 110
 1345 ms 74632 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17612 KB Output is correct
2 Correct 18 ms 17484 KB Output is correct
3 Correct 22 ms 17428 KB Output is correct
4 Correct 18 ms 17488 KB Output is correct
5 Correct 18 ms 17412 KB Output is correct
6 Correct 18 ms 17476 KB Output is correct
7 Correct 20 ms 17404 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17612 KB Output is correct
2 Correct 18 ms 17484 KB Output is correct
3 Correct 22 ms 17428 KB Output is correct
4 Correct 18 ms 17488 KB Output is correct
5 Correct 18 ms 17412 KB Output is correct
6 Correct 18 ms 17476 KB Output is correct
7 Correct 20 ms 17404 KB Output is correct
8 Correct 100 ms 28868 KB Output is correct
9 Correct 20 ms 20972 KB Output is correct
10 Correct 17 ms 20044 KB Output is correct
11 Correct 97 ms 28776 KB Output is correct
12 Correct 113 ms 28932 KB Output is correct
13 Correct 102 ms 29156 KB Output is correct
14 Correct 110 ms 29252 KB Output is correct
15 Correct 99 ms 29208 KB Output is correct
16 Correct 107 ms 29212 KB Output is correct
17 Correct 113 ms 29212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17612 KB Output is correct
2 Correct 18 ms 17484 KB Output is correct
3 Correct 22 ms 17428 KB Output is correct
4 Correct 18 ms 17488 KB Output is correct
5 Correct 18 ms 17412 KB Output is correct
6 Correct 18 ms 17476 KB Output is correct
7 Correct 20 ms 17404 KB Output is correct
8 Correct 100 ms 28868 KB Output is correct
9 Correct 20 ms 20972 KB Output is correct
10 Correct 17 ms 20044 KB Output is correct
11 Correct 97 ms 28776 KB Output is correct
12 Correct 113 ms 28932 KB Output is correct
13 Correct 102 ms 29156 KB Output is correct
14 Correct 110 ms 29252 KB Output is correct
15 Correct 99 ms 29208 KB Output is correct
16 Correct 107 ms 29212 KB Output is correct
17 Correct 113 ms 29212 KB Output is correct
18 Correct 1221 ms 73536 KB Output is correct
19 Correct 28 ms 30404 KB Output is correct
20 Correct 36 ms 32852 KB Output is correct
21 Correct 1190 ms 74580 KB Output is correct
22 Correct 1345 ms 74580 KB Output is correct
23 Correct 1170 ms 74536 KB Output is correct
24 Correct 1311 ms 74580 KB Output is correct
25 Correct 1200 ms 74632 KB Output is correct
26 Correct 1233 ms 74588 KB Output is correct
27 Correct 1321 ms 74564 KB Output is correct