Submission #41933

#	Time	Username	Problem	Language	Result	Execution time	Memory
41933		aome	Snake Escaping (JOI18_snake_escaping)	C++14	Compilation error	0 ms	0 KiB

snake_escaping

include <bits/stdc++.h>

using namespace std;

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

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:1:1: error: 'include' does not name a type
 include <bits/stdc++.h>
 ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:45:30: error: 'scanf' was not declared in this scope
  scanf("%d %d %s", &n, &q, &a);
                              ^
snake_escaping.cpp:48:28: error: 'max' was not declared in this scope
   for (int j = max(0, n - 6); j < n; ++j) { // first 7 bits
                            ^
snake_escaping.cpp:53:35: error: 'max' was not declared in this scope
   for (int j = 0; j < max(0, n - 6); ++j) { // last 13 bits
                                   ^
snake_escaping.cpp:61:24: error: 'memset' was not declared in this scope
   memset(f, 0, sizeof f);
                        ^
snake_escaping.cpp:62:41: error: 'max' was not declared in this scope
   for (int j = 0; j < (1 << max(0, n - 6)); ++j) {
                                         ^
snake_escaping.cpp:70:51: error: 'printf' was not declared in this scope
  for (int i = 0; i < q; ++i) printf("%d\n", res[i]);
                                                   ^