Submission #944481

#	Time	Username	Problem	Language	Result	Execution time	Memory
944481		rainboy	백신 (KOI13_vaccine)	C11	24 / 24	15 ms	1628 KiB

vaccine

#include <stdio.h>

#define N	1000
#define K	100
#define M	(N * K)
#define MD	0x7fffffff

unsigned int Z = 12345;

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

int X = 123123123, Y = 987987987;

int ppx[N + 1], ppy[N + 1];

void init() {
	int i;

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

int xx[M], yy[M], gg[M];

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

		while (j < k) {
			int c = xx[hh[j]] != xx[h] ? (xx[hh[j]] < xx[h] ? -1 : 1) : (yy[hh[j]] != yy[h] ? (yy[hh[j]] < yy[h] ? -1 : 1) : 0);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int main() {
	static int aa[N], xx1[N], yy1[N], xx2[N], yy2[N], hh[M];
	static char used[K];
	int n, m, k, l, x, y, g, h, h_, h1, i, cnt;

	init();
	scanf("%d%d", &k, &l);
	m = 0;
	for (g = 0; g < k; g++) {
		scanf("%d", &n);
		for (i = 0; i < n; i++)
			scanf("%d", &aa[i]);
		x = 0, y = 0;
		for (i = 0; i < n; i++) {
			x = ((long long) x * X + aa[i]) % MD;
			y = ((long long) y * Y + aa[i]) % MD;
			if (i >= l - 1) {
				xx1[i - l + 1] = x, yy1[i - l + 1] = y;
				x = (x + (long long) (MD - aa[i - l + 1]) * ppx[l - 1]) % MD;
				y = (y + (long long) (MD - aa[i - l + 1]) * ppy[l - 1]) % MD;
			}
		}
		x = 0, y = 0;
		for (i = n - 1; i >= 0; i--) {
			x = ((long long) x * X + aa[i]) % MD;
			y = ((long long) y * Y + aa[i]) % MD;
			if (i + l <= n) {
				xx2[i] = x, yy2[i] = y;
				x = (x + (long long) (MD - aa[i + l - 1]) * ppx[l - 1]) % MD;
				y = (y + (long long) (MD - aa[i + l - 1]) * ppy[l - 1]) % MD;
			}
		}
		for (i = 0; i + l <= n; i++)
			if (xx1[i] < xx2[i] || xx1[i] == xx2[i] && yy1[i] < yy2[i])
				xx[m] = xx1[i], yy[m] = yy1[i], gg[m] = g, m++;
			else
				xx[m] = xx2[i], yy[m] = yy2[i], gg[m] = g, m++;
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	for (h = 0; h < m; h = h_) {
		h_ = h, x = xx[hh[h]], y = yy[hh[h]], cnt = 0;
		while (h_ < m && xx[hh[h_]] == x && yy[hh[h_]] == y) {
			g = gg[hh[h_++]];
			if (!used[g])
				used[g] = 1, cnt++;
		}
		if (cnt == k) {
			printf("YES\n");
			return 0;
		}
		for (h1 = h; h1 < h_; h1++) {
			g = gg[hh[h1]];
			used[g] = 0;
		}
	}
	printf("NO\n");
	return 0;
}

Compilation message (stderr)

vaccine.c: In function 'main':
vaccine.c:85:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |    if (xx1[i] < xx2[i] || xx1[i] == xx2[i] && yy1[i] < yy2[i])
      |                           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
vaccine.c:58:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d%d", &k, &l);
      |  ^~~~~~~~~~~~~~~~~~~~~
vaccine.c:61:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
vaccine.c:63:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |    scanf("%d", &aa[i]);
      |    ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 2.64 / 2.64
• Subtask 2: 3.12 / 3.12
• Subtask 3: 3.6 / 3.6
• Subtask 4: 4.32 / 4.32
• Subtask 5: 4.8 / 4.8
• Subtask 6: 5.52 / 5.52