Submission #42154

#	Time	Username	Problem	Language	Result	Execution time	Memory
42154		fest	Snake Escaping (JOI18_snake_escaping)	C++14	65 / 100	2065 ms	65536 KiB

snake_escaping

// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("1.out", "w", stdout);
	#else
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 20, inf = 1e9 * 2, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

int built[1 << N], ones[21], dp[2][2][1 << N], cost[2][1 << N], qs[21];

int n;

int rev(int x) {
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (x & (1 << i)) continue;
		ret |= (1 << i);
	} 
	return ret;
}

void build(int ty) {
	for (int mask = 0; mask < (1 << n); mask++) {
		dp[ty][0][mask] += cost[ty][mask];
		if (mask & 1) dp[ty][0][mask] += cost[ty][mask ^ 1];
	}		
	for (int bit = 1; bit < n; bit++) {
		int j = bit % 2;
		for (int mask = 0; mask < (1 << n); mask++) {
			dp[ty][j][mask] = dp[ty][j ^ 1][mask];
			if (mask & (1 << bit)) dp[ty][j][mask] += dp[ty][j ^ 1][mask ^ (1 << bit)];
		}
	}
}

int calc(int ty, int cnt) {
	int ret = 0;
	int alw = 0;
	int r = 0;
	for (int i = 0; i < n; i++) {
		if (qs[i] == 2) alw |= (1 << i);
		if (qs[i] == 1) ones[r++] = i;
	}
	for (int mask = 0; mask < (1 << cnt); mask++) {
		int now = alw;
		for (int i = 0; i < r; i++) {
			if (mask & (1 << i)) now |= (1 << ones[i]);
		}
		if (built[mask] % 2) ret -= dp[ty][(n - 1) % 2][now];
		else ret += dp[ty][(n - 1) % 2][now];
	}	
	return abs(ret);
} 

int main() {
  
	int q;
	cin >> n >> q;
	scanf("\n");
	for (int i = 0; i < (1 << n); i++) {
		char x;
		scanf("%c", &x);
		cost[0][i] = (int)(x - '0');
		cost[1][rev(i)] = (int)(x - '0');
	} 
	for (int mask = 0; mask < (1 << n); mask++) built[mask] = __builtin_popcount(mask);
	build(0);
	build(1);
	while (q--) {
		scanf("\n");
		int zer = 0, one = 0, que = 0;
		for (int i = n - 1; i >= 0; i--) {
			char x;
			scanf("%c", &x);
			if (x == '?') qs[i] = 2, que++;
			if (x == '1') qs[i] = 1, one++;
			if (x == '0') qs[i] = 0, zer++;
		}
		if (que < 8) {
			int ans = 0;
			int r = 0;
			int alw = 0;
			for (int i = 0; i < n; i++) {
				if (qs[i] == 2) ones[r++] = i; 
				if (qs[i] == 1) alw |= (1 << i);
			}
			for (int mask = 0; mask < (1 << que); mask++) {
				int ret = alw;
				for (int i = 0; i < r; i++) {
					if (mask & (1 << i)) ret |= (1 << ones[i]);
				}
				ans += cost[0][ret];
			}
			printf("%d\n", ans);
			continue;
		}
		if (!one) {
			int ret = 0;
			for (int i = 0; i < n; i++) {
				if (qs[i] == 2) ret |= (1 << i);
			}
			printf("%d\n", dp[0][(n - 1) % 2][ret]);
			continue;
		}
		if (!zer) {
			int ret = 0;
			for (int i = 0; i < n; i++) {
				if (qs[i] == 2) ret |= (1 << i);
			}
			printf("%d\n", dp[1][(n - 1) % 2][ret]);
			continue;
		}
		if (one < 8) {
			printf("%d\n", calc(0, one));
			continue;
		}
		for (int i = 0; i < n; i++) if (qs[i] < 2) qs[i] ^= 1;
		printf("%d\n", calc(1, zer));
	}
	return 0;	
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void FREOPEN()':
snake_escaping.cpp:25:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
                                     ^
snake_escaping.cpp:26:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
                                       ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:91:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("\n");
             ^
snake_escaping.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &x);
                  ^
snake_escaping.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n");
              ^
snake_escaping.cpp:106:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%c", &x);
                   ^

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