Submission #544745

#	Time	Username	Problem	Language	Result	Execution time	Memory
544745		rainboy	Nautilus (BOI19_nautilus)	C11	100 / 100	251 ms	1100 KiB

nautilus

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

#define N	500
#define M	500
#define L	5000
#define B	60
#define K	4167	/* K = ceil(N * M / B) */

void and_(long long *aa, long long *bb, long long *cc) {
	int i;

	for (i = 0; i < K; i++)
		cc[i] = aa[i] & bb[i];
}

void or_(long long *aa, long long *bb, long long *cc) {
	int i;

	for (i = 0; i < K; i++)
		cc[i] = aa[i] | bb[i];
}

void shift_(long long *aa, int k) {
	int i, q, r;

	if (k > 0) {
		q = k / B, r = k % B;
		for (i = K - 1; i >= 0; i--) {
			long long a = aa[i];

			aa[i] = 0;
			if (i + q < K) {
				aa[i + q] |= (a & (1LL << B - r) - 1) << r;
				if (i + q + 1 < K)
					aa[i + q + 1] |= a >> B - r;
			}
		}
	} else {
		q = -k / B, r = -k % B;
		for (i = 0; i < K; i++) {
			long long a = aa[i];

			aa[i] = 0;
			if (i - q >= 0) {
				aa[i - q] |= a >> r;
				if (i - q > 0)
					aa[i - q - 1] |= (a & (1LL << r) - 1) << B - r;
			}
		}
	}
}

int main() {
	static char cc[N][M + 1], dd[L + 1];
	static long long aa[K], bb[K], tt[K], tt_[K], nn[K], ss[K], ww[K], ee[K];
	int n, m, l, h, i, j, ans;

	scanf("%d%d%d", &n, &m, &l);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			if (cc[i][j] == '.')
				aa[(i * m + j) / B] |= 1LL << (i * m + j) % B, bb[(i * m + j) / B] |= 1LL << (i * m + j) % B;
			if (i > 0)
				nn[(i * m + j) / B] |= 1LL << (i * m + j) % B;
			if (i + 1 < n)
				ss[(i * m + j) / B] |= 1LL << (i * m + j) % B;
			if (j > 0)
				ww[(i * m + j) / B] |= 1LL << (i * m + j) % B;
			if (j + 1 < m)
				ee[(i * m + j) / B] |= 1LL << (i * m + j) % B;
		}
	scanf("%s", dd);
	for (h = 0; h < l; h++)
		if (dd[h] == 'N')
			and_(aa, nn, tt), shift_(tt, -m), and_(tt, bb, aa);
		else if (dd[h] == 'S')
			and_(aa, ss, tt), shift_(tt, m), and_(tt, bb, aa);
		else if (dd[h] == 'W')
			and_(aa, ww, tt), shift_(tt, -1), and_(tt, bb, aa);
		else if (dd[h] == 'E')
			and_(aa, ee, tt), shift_(tt, 1), and_(tt, bb, aa);
		else {
			memset(tt_, 0, sizeof tt_);
			and_(aa, nn, tt), shift_(tt, -m), or_(tt_, tt, tt_);
			and_(aa, ss, tt), shift_(tt, m), or_(tt_, tt, tt_);
			and_(aa, ww, tt), shift_(tt, -1), or_(tt_, tt, tt_);
			and_(aa, ee, tt), shift_(tt, 1), or_(tt_, tt, tt_);
			and_(tt_, bb, aa);
		}
	ans = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (aa[(i * m + j) / B] & 1LL << (i * m + j) % B)
				ans++;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

nautilus.c: In function 'shift_':
nautilus.c:34:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |     aa[i + q] |= (a & (1LL << B - r) - 1) << r;
      |                                 ^
nautilus.c:34:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   34 |     aa[i + q] |= (a & (1LL << B - r) - 1) << r;
      |                       ~~~~~~~~~~~~~~~^~~
nautilus.c:36:30: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   36 |      aa[i + q + 1] |= a >> B - r;
      |                              ^
nautilus.c:48:39: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   48 |      aa[i - q - 1] |= (a & (1LL << r) - 1) << B - r;
      |                            ~~~~~~~~~~~^~~
nautilus.c:48:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |      aa[i - q - 1] |= (a & (1LL << r) - 1) << B - r;
      |                                                 ^
nautilus.c: In function 'main':
nautilus.c:59:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d%d%d", &n, &m, &l);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
nautilus.c:61:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~
nautilus.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%s", dd);
      |  ^~~~~~~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 34 / 34