Submission #544740

#	Time	Username	Problem	Language	Result	Execution time	Memory
544740		rainboy	Genetics (BOI18_genetics)	C11	100 / 100	723 ms	33392 KiB

genetics

#include <stdio.h>

#define N	4100
#define M	4100
#define MD	0x7fffffff
#define X	12345
#define Y	54321

int px[N], py[N];

void init() {
	int i;

	px[0] = py[0] = 1;
	for (i = 1; i < N; i++) {
		px[i] = (long long) px[i - 1] * X % MD;
		py[i] = (long long) py[i - 1] * Y % MD;
	}
}

int main() {
	static char cc[N][M + 1];
	static long long xx[N], yy[N];
	int n, m, d_, h, i, j, x, y;

	init();
	scanf("%d%d%d", &n, &m, &d_);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++) {
		xx[i] = (long long) px[i] * d_ % MD;
		yy[i] = (long long) py[i] * d_ % MD;
	}
	for (h = 0; h < m; h++) {
		int ax, cx, gx, tx, ay, cy, gy, ty;
		long long sx, sy;

		ax = ay = cx = cy = gx = gy = tx = ty = 0;
		for (i = 0; i < n; i++)
			if (cc[i][h] == 'A')
				ax = ((long long) ax + px[i]) % MD, ay = ((long long) ay + py[i]) % MD;
			else if (cc[i][h] == 'C')
				cx = ((long long) cx + px[i]) % MD, cy = ((long long) cy + py[i]) % MD;
			else if (cc[i][h] == 'G')
				gx = ((long long) gx + px[i]) % MD, gy = ((long long) gy + py[i]) % MD;
			else if (cc[i][h] == 'T')
				tx = ((long long) tx + px[i]) % MD, ty = ((long long) ty + py[i]) % MD;
		sx = (long long) ax + cx + gx + tx, sy = (long long) ay + cy + gy + ty;
		for (i = 0; i < n; i++)
			if (cc[i][h] == 'A')
				xx[i] = ((long long) xx[i] + sx - ax) % MD, yy[i] = ((long long) yy[i] + sy - ay) % MD;
			else if (cc[i][h] == 'C')
				xx[i] = ((long long) xx[i] + sx - cx) % MD, yy[i] = ((long long) yy[i] + sy - cy) % MD;
			else if (cc[i][h] == 'G')
				xx[i] = ((long long) xx[i] + sx - gx) % MD, yy[i] = ((long long) yy[i] + sy - gy) % MD;
			else if (cc[i][h] == 'T')
				xx[i] = ((long long) xx[i] + sx - tx) % MD, yy[i] = ((long long) yy[i] + sy - ty) % MD;
	}
	x = y = 0;
	for (i = 0; i < n; i++)
		x = (x + (long long) px[i] * d_) % MD, y = (y + (long long) py[i] * d_) % MD;
	for (i = 0; i < n; i++)
		if (xx[i] == x && yy[i] == y) {
			for (j = 0; j < n; j++)
				if (j != i) {
					int d;

					d = 0;
					for (h = 0; h < m; h++)
						if (cc[i][h] != cc[j][h])
							if (d++ == d_)
								goto out;
out:
					if (d != d_)
						break;
				}
			if (j == n) {
				printf("%d\n", i + 1);
				return 0;
			}
		}
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26