Submission #41154

#	Time	Username	Problem	Language	Result	Execution time	Memory
41154		aome	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2041 ms	35088 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;
const int M = 1594323;

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

void prepare() {
	for (int i = 0; i < (1 << 13); ++i) {
		for (int j = 12; j >= 0; --j) {
			to3[i] *= 3;
			if (i >> j & 1) to3[i]++;
		}
	}
	pw3[0] = 1; 
	for (int i = 1; i < 13; ++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 < 13; ++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]]];
		}
	}
}

inline bool check(int mask, int i) {
	return (mask & mask2[0][i]) == mask2[0][i] && (mask | mask2[1][i]) == mask2[1][i];
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> q >> a; 
	for (int i = 0; i < q; ++i) {
		string s; cin >> s;
		for (int j = max(0, n - 7); 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 - 7); ++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 < 128; ++i) { // first 7 bits
		memset(f, 0, sizeof f);
		for (int j = 0; j < (1 << n); ++j) {
			if ((j & 127) != i) continue;
			f[to3[j >> 7]] += a[j] - '0';
		}
		calc();
		for (int j = 0; j < q; ++j) {
			if (!check(i, j)) continue;
			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 'void prepare()':
snake_escaping.cpp:24:54: warning: iteration 11u invokes undefined behavior [-Waggressive-loop-optimizations]
  for (int i = 1; i < 13; ++i) pw3[i] = 3 * pw3[i - 1];
                                                      ^
snake_escaping.cpp:24:20: note: containing loop
  for (int i = 1; i < 13; ++i) pw3[i] = 3 * pw3[i - 1];
                    ^

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