Submission #41941

#	Time	Username	Problem	Language	Result	Execution time	Memory
41941		aome	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1603 ms	65536 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 20;
const int M = 3000005;

int n, q;
int to3[1 << 14];
int mask2[2][N]; // 0 check and, 1 check or
int mask3[N];
int res[N];
int pw3[13], f[M], g[M];
char a[N];

void prepare() {
	for (int i = 0; i < (1 << 14); ++i) {
		for (int j = 13; j >= 0; --j) {
			to3[i] *= 3;
			if (i >> j & 1) to3[i]++;
		}
	}
	pw3[0] = 1;
	for (int i = 1; i < 14; ++i) pw3[i] = 3 * pw3[i - 1];
	for (int i = 0; i < M; ++i) {
		int cur = i;
		g[i] = -1;
		for (int j = 0; j < 14; ++j) {
			if (cur % 3 == 2) g[i] = j;
			cur /= 3;
		}
	}
}

void calc() {
	for (int i = 0; i < M; ++i) {
		if (g[i] != -1) {
			f[i] += f[i - 2 * pw3[g[i]]];
			f[i] += f[i - 1 * pw3[g[i]]];
		}
	}
}

int main() {
	scanf("%d %d %s", &n, &q, &a);
	for (int i = 0; i < q; ++i) {
		char s[20]; scanf("%s", &s);
		for (int j = max(0, n - 6); j < n; ++j) { // first 7 bits
			mask2[0][i] <<= 1, mask2[1][i] <<= 1;
			if (s[j] == '1') mask2[0][i]++;
			if (s[j] == '?' || s[j] == '1') mask2[1][i]++;
		}
		for (int j = 0; j < max(0, n - 6); ++j) { // last 13 bits
			mask3[i] *= 3;
			if (s[j] == '1') mask3[i]++;
			if (s[j] == '?') mask3[i] += 2;
		}
	}
	prepare();
	for (int i = 0; i < 64; ++i) { // first 7 bits
		memset(f, 0, sizeof f);
		for (int j = 0; j < (1 << max(0, n - 6)); ++j) {
			f[to3[j]] += a[j << 6 | i] - '0';
		}
		calc();
		for (int j = 0; j < q; ++j) {
			if ((i & mask2[0][j]) == mask2[0][j] && (i | mask2[1][j]) == mask2[1][j]) res[j] += f[mask3[j]];
		}
	}
	for (int i = 0; i < q; ++i) printf("%d\n", res[i]);
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:45:30: warning: format '%s' expects argument of type 'char*', but argument 4 has type 'char (*)[1048576]' [-Wformat=]
  scanf("%d %d %s", &n, &q, &a);
                              ^
snake_escaping.cpp:47:29: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[20]' [-Wformat=]
   char s[20]; scanf("%s", &s);
                             ^
snake_escaping.cpp:45:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %s", &n, &q, &a);
                               ^
snake_escaping.cpp:47:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char s[20]; scanf("%s", &s);
                              ^
snake_escaping.cpp: In function 'void prepare()':
snake_escaping.cpp:24:54: warning: iteration 12u invokes undefined behavior [-Waggressive-loop-optimizations]
  for (int i = 1; i < 14; ++i) pw3[i] = 3 * pw3[i - 1];
                                                      ^
snake_escaping.cpp:24:20: note: containing loop
  for (int i = 1; i < 14; ++i) pw3[i] = 3 * pw3[i - 1];
                    ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25