Submission #448566

#	Time	Username	Problem	Language	Result	Execution time	Memory
448566		rainboy	Osmosmjerka (COCI17_osmosmjerka)	C11	160 / 160	223 ms	18364 KiB

osmosmjerka

#include <stdio.h>

#define N	500
#define M	500
#define N1	(N * M * 8)
#define L	(N * M)
#define A	26
#define MD	0x7fffffff

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

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int X, Y, ppx[L], ppy[L];

void init() {
	int i;

	X = rand_() % (MD - A) + A, Y = rand_() % (MD - A) + A;
	ppx[0] = ppy[0] = 1;
	for (i = 1; i < L; i++) {
		ppx[i] = (long long) ppx[i - 1] * X % MD;
		ppy[i] = (long long) ppy[i - 1] * Y % MD;
	}
}

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

long long aa[N1]; int n_, k, r, px, py, n1;

void solve(char *cc) {
	int i, x, y, x_, y_;

	x_ = 0, y_ = 0, x = 0, y = 0;
	for (i = 0; i < n_; i++) {
		int c = cc[i] - 'a';

		x_ = ((long long) x_ * X + c) % MD, y_ = ((long long) y_ * Y + c) % MD;
		if (i < r)
			x = ((long long) x * X + c) % MD, y = ((long long) y * Y + c) % MD;
	}
	for (i = 0; i < n_; i++) {
		int x1 = ((long long) x_ * px + x) % MD, y1 = ((long long) y_ * py + y) % MD, c;

		aa[n1++] = (long long) x1 * MD + y1;
		c = cc[i] - 'a';
		x_ = (x_ - (long long) c * ppx[n_ - 1] % MD + MD) % MD, y_ = (y_ - (long long) c * ppy[n_ - 1] % MD + MD) % MD;
		x_ = ((long long) x_ * X + c) % MD, y_ = ((long long) y_ * Y + c) % MD;
		if (r > 0) {
			x = (x - (long long) c * ppx[r - 1] % MD + MD) % MD, y = (y - (long long) c * ppy[r - 1] % MD + MD) % MD;
			c = cc[(i + r) % n_] - 'a';
			x = ((long long) x * X + c) % MD, y = ((long long) y * Y + c) % MD;
		}
	}
}

void sort(long long *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		long long a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

int main() {
	static char cc[N][M + 1], s[L + 1];
	int n, m, l, h, i, j;
	long long p, q, d;

	init();
	scanf("%d%d%d", &n, &m, &k), d = gcd(n, m), l = n * m / d, k = min(k, l);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	n_ = m, r = k % n_, px = 0, py = 0;
	for (j = r; j < k; j += n_)
		px = ((long long) px + ppx[j]) % MD, py = ((long long) py + ppy[j]) % MD;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++)
			s[j] = cc[i][j];
		solve(s);
		for (j = 0; j < m; j++)
			s[j] = cc[i][m - 1 - j];
		solve(s);
	}
	n_ = n, r = k % n_, px = 0, py = 0;
	for (j = r; j < k; j += n_)
		px = ((long long) px + ppx[j]) % MD, py = ((long long) py + ppy[j]) % MD;
	for (j = 0; j < m; j++) {
		for (i = 0; i < n; i++)
			s[i] = cc[i][j];
		solve(s);
		for (i = 0; i < n; i++)
			s[i] = cc[n - 1 - i][j];
		solve(s);
	}
	n_ = l, r = k % n_, px = 0, py = 0;
	for (j = r; j < k; j += n_)
		px = ((long long) px + ppx[j]) % MD, py = ((long long) py + ppy[j]) % MD;
	for (j = 0; j < d; j++) {
		for (h = 0; h < l; h++)
			s[h] = cc[h % n][(j + h) % m];
		solve(s);
		for (h = 0; h < l; h++)
			s[h] = cc[h % n][m - 1 - (j + h) % m];
		solve(s);
		for (h = 0; h < l; h++)
			s[h] = cc[n - 1 - h % n][(j + h) % m];
		solve(s);
		for (h = 0; h < l; h++)
			s[h] = cc[n - 1 - h % n][m - 1 - (j + h) % m];
		solve(s);
	}
	sort(aa, 0, n1);
	p = 0, q = (long long) n1 * n1;
	for (i = 0; i < n1; i = j) {
		j = i + 1;
		while (j < n1 && aa[j] == aa[i])
			j++;
		p += (long long) (j - i) * (j - i);
	}
	d = gcd(p, q), p /= d, q /= d;
	printf("%lld/%lld\n", p, q);
	return 0;
}

Compilation message (stderr)

osmosmjerka.c: In function 'main':
osmosmjerka.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d%d%d", &n, &m, &k), d = gcd(n, m), l = n * m / d, k = min(k, l);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
osmosmjerka.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160