Submission #494190

#	Time	Username	Problem	Language	Result	Execution time	Memory
494190		rainboy	L-triominoes (CEOI21_ltriominoes)	C11	100 / 100	2115 ms	580 KiB

ltrominoes

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

#define N	13
#define M	1000
#define R	20
#define K	250

unsigned int X = 12345;

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

void advance(char *dp, int n, int c) {
	static char dq[N][1 << N + 1];
	int i, b;

	for (i = 0; i < n; i++)
		memset(dq[i], 0, (1 << n + 1) * sizeof *dq[i]);
	for (b = 0; b < 1 << n; b++)
		if (dp[b]) {
			dq[0][b << 1 | (c & 1)] = 1;
			if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
				dq[0][b << 1 | 1 << n | 1 << n - 1 | 1 << 0] = 1;
		}
	for (i = 0; i + 1 < n; i++)
		for (b = 0; b < 1 << n + 1; b++)
			if (dq[i][b]) {
				int b_ = b << 1 & (1 << n + 1) - 1;

				if ((c & 1 << i + 1) != 0) {
					if ((b & 1 << n) != 0)
						dq[i + 1][b_ | 1 << 0] = 1;
				} else if ((b & 1 << n) != 0) {
					dq[i + 1][b_] = 1;
					if ((b & 1 << 0) == 0 && (b & 1 << n - 1) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << 1 | 1 << n] = 1;
					if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << n - 1 | 1 << n] = 1;
				} else {
					if ((b & 1 << 0) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << 1] = 1;
					if ((b & 1 << n - 1) == 0)
						dq[i + 1][b_ | 1 << 0 | 1 << n] = 1;
				}
			}
	memset(dp, 0, (1 << n) * sizeof *dp);
	for (b = 0; b < 1 << n; b++)
		if (dq[n - 1][b | 1 << n])
			dp[b] = 1;
}

int ii[K], jj[K];

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)
			if (jj[hh[j]] == jj[h])
				j++;
			else if (jj[hh[j]] < jj[h]) {
				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;
	}
}

void advance0(char *dp, int n, int k) {
	if (k >= R)
		k -= ((k - R) / 6 + 1) * 6;
	while (k--)
		advance(dp, n, 0);
}

int main() {
#if 0
	static char dp_[R][1 << N];
	int n, b;

	for (n = 1; n <= 13; n++) {
		printf("trying %d\n", n);
		for (b = 0; b < 1 << n; b++) {
			int b_, h;

			memset(dp_[0], 0, (1 << n) * sizeof *dp_[0]), dp_[0][b] = 1;
			for (h = 1; h < R; h++) {
				memcpy(dp_[h], dp_[h - 1], (1 << n) * sizeof *dp_[h - 1]);
				advance(dp_[h], n, 0);
			}
			for (b_ = 0; b_ < 1 << n; b_++)
				if (dp_[R - 1][b_] != dp_[R - 7][b_]) {
					printf("conjecture disproven :(\n");
					return 0;
				}
		}
	}
#else
	static char dp[1 << N];
	static int hh[K];
	int n, m, k, h, h_, j, j_, b;

	scanf("%d%d%d", &n, &m, &k);
	for (h = 0; h < k; h++) {
		scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
		hh[h] = h;
	}
	sort(hh, 0, k);
	dp[(1 << n) - 1] = 1;
	for (h = 0, j = -1; h < k; h = h_) {
		j_ = jj[hh[h]];
		h_ = h;
		b = 0;
		while (h_ < k && jj[hh[h_]] == j_)
			b |= 1 << ii[hh[h_++]];
		advance0(dp, n, j_ - 1 - j), advance(dp, n, b);
		j = j_;
	}
	advance0(dp, n, m - 1 - j);
	printf(dp[(1 << n) - 1] ? "YES\n" : "NO\n");
#endif
	return 0;
}

Compilation message (stderr)

ltrominoes.c: In function 'advance':
ltrominoes.c:16:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   16 |  static char dq[N][1 << N + 1];
      |                      ^~
ltrominoes.c:20:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   20 |   memset(dq[i], 0, (1 << n + 1) * sizeof *dq[i]);
      |                          ~~^~~
ltrominoes.c:24:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |    if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                  ~~^~~
ltrominoes.c:24:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |    if ((c & 1) == 0 && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                                           ~~^~~
ltrominoes.c:25:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |     dq[0][b << 1 | 1 << n | 1 << n - 1 | 1 << 0] = 1;
      |                                  ~~^~~
ltrominoes.c:28:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   28 |   for (b = 0; b < 1 << n + 1; b++)
      |                        ~~^~~
ltrominoes.c:30:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   30 |     int b_ = b << 1 & (1 << n + 1) - 1;
      |                             ~~^~~
ltrominoes.c:30:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |     int b_ = b << 1 & (1 << n + 1) - 1;
      |                       ~~~~~~~~~~~~~^~~
ltrominoes.c:32:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   32 |     if ((c & 1 << i + 1) != 0) {
      |                   ~~^~~
ltrominoes.c:37:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   37 |      if ((b & 1 << 0) == 0 && (b & 1 << n - 1) == 0)
      |                                         ~~^~~
ltrominoes.c:39:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |      if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                 ~~^~~
ltrominoes.c:39:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |      if (i + 2 < n && (b & 1 << n - 1) == 0 && (b & 1 << n - 2) == 0)
      |                                                          ~~^~~
ltrominoes.c:40:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |       dq[i + 1][b_ | 1 << 0 | 1 << n - 1 | 1 << n] = 1;
      |                                    ~~^~~
ltrominoes.c:44:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |      if ((b & 1 << n - 1) == 0)
      |                    ~~^~~
ltrominoes.c: In function 'main':
ltrominoes.c:109:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
ltrominoes.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20