oj.uz

Submission #544287

# Submission time Handle Problem Language Result Execution time Memory
544287 2022-04-01T15:08:58 Z valerikk Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 2 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int L = 21;
const int M = (1 << L) + 7;
const int K = 6;

int l, q;
int m;
char s[M];
int a[M];
int f[M];
int g[M];

int main() {
	cin >> l >> q >> s;

	m = (1 << l);
	for (int i = 0; i < m; ++i) {
		a[i] = s[i] - '0';
	}

	for (int i = 0; i < m; ++i) {
		f[i] = a[i];
		g[i] = a[i];
	}	
	for (int j = 0; j < l; ++j) {
		for (int i = 0; i < m; ++i) {
			if ((i >> j) & 1) {
				f[i] += f[i ^ (1 << j)];
				g[i ^ (1 << j)] += g[i];
			}
		}
	}

	while (q--) {
		/* int x;
		scanf("%d", &x); */
		static int t[3];
		memset(t, 0, sizeof(t));
		string tt;
		cin >> tt;
		for (int i = l - 1; i >= 0; --i) {
			/* t[x % 3] |= (1 << i);
			x /= 3; */
			t[tt[i] == '?' ? 2 : tt[i] - '0'] |= (1 << i); 
		}

		if (__builtin_popcount(t[1]) <= K) {
			int ans = 0;
			int ppc = __builtin_popcount(t[1]);
			for (int z = t[1]; ; z = (z - 1) & t[1]) {
				ans += (((ppc ^ __builtin_popcount(z)) & 1) ? -1 : 1) * f[t[2] | z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		} else if (__builtin_popcount(t[0]) <= K) {
			int ans = 0;
			int ppc = __builtin_popcount(t[0]);
			for (int z = t[0]; ; z = (z - 1) & t[0]) {
				ans += (((ppc ^ __builtin_popcount(z)) & 1) ? -1 : 1) * g[t[1] ^ t[0] ^ z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		} else {
			assert(__builtin_popcount(t[2]) <= K);
			int ans = 0;
			for (int z = t[2]; ; z = (z - 1) & t[2]) {
				ans += a[t[1] | z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -