Submission #535331

#	Time	Username	Problem	Language	Result	Execution time	Memory
535331		amunduzbaev	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	909 ms	65536 KiB

snake_escaping

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
 
const int N = 20;
int dp[2][1 << N ][N];
int a[1 << N];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<(1 << n);i++){
		char c; cin>>c;
		a[i] = c - '0';
	}
	for(int mask=(1 << n) - 1;~mask;mask--){
		int res = a[mask];
		for(int i=n-1;~i;i--){
			if(!(mask >> i & 1)){
				res += dp[0][mask | (1 << i)][i];
			}
			dp[0][mask][i] = res;
		}
	}
	
	for(int mask=0;mask<(1 << n);mask++){
		int res = a[mask];
		for(int i=n-1;~i;i--){
			if(mask >> i & 1){
				res += dp[1][mask ^ (1 << i)][i];
			}
			dp[1][mask][i] = res;
		}
	}
	
	ar<int, 2> c {};
	int res, in, t;
	vector<int> p;
	while(m--){
		string s; cin>>s;
		reverse(s.begin(), s.end());
		c[0] = c[1] = c[2] = 0;
		for(int i=0;i<n;i++){
			if(s[i] == '0') c[0]++;
			if(s[i] == '1') c[1]++;
			if(s[i] == '?') c[2]++;
		}
		
		res = 0; p.clear();
		if(c[2] <= 6){
			in = 0;
			for(int i=0;i<n;i++){
				if(s[i] == '0' || s[i] == '1') in |= ((s[i] - '0') << i);
				else p.push_back(i);
			}
			
			for(int mask=0;mask < (1 << c[2]);mask++){
				int tot = in;
				for(int j=0;j<c[2];j++){
					if(mask >> j & 1) tot |= (1 << p[j]);
				}
				
				res += a[tot];
			}
		} 
		else if(c[0] <= 6) {
			t = 0, in = 0;
			for(int i=0;i<n;i++){
				if(s[i] == '1') in |= (1 << i);
				if(s[i] == '0') p.push_back(i);
			}
			
			for(int mask=0;mask < (1 << c[0]);mask++){
				int tot = in;
				for(int j=0;j<c[0];j++){
					if(mask >> j & 1) tot |= (1 << p[j]);
				}
				
				if(__builtin_popcount(mask)&1) res -= dp[t][tot][0];
				else res += dp[t][tot][0];
			}
		} else {
			t = 1, in = (1 << n) - 1;
			for(int i=0;i<n;i++){
				if(s[i] == '0') in ^= (1 << i);
				if(s[i] == '1') p.push_back(i);
			}
			
			for(int mask=0;mask<(1 << c[1]);mask++){
				int tot = in;
				for(int j=0;j<c[1];j++){
					if(mask >> j & 1) tot ^= (1 << p[j]);
				}
				
				if(__builtin_popcount(mask)&1) res -= dp[t][tot][0];
				else res += dp[t][tot][0];
			}
		}
		
		cout<<res<<"\n";
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:44:22: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
   44 |   c[0] = c[1] = c[2] = 0;
snake_escaping.cpp:38:13: note: while referencing 'c'
   38 |  ar<int, 2> c {};
      |             ^
snake_escaping.cpp:48:24: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
   48 |    if(s[i] == '?') c[2]++;
snake_escaping.cpp:38:13: note: while referencing 'c'
   38 |  ar<int, 2> c {};
      |             ^
snake_escaping.cpp:48:24: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
   48 |    if(s[i] == '?') c[2]++;
snake_escaping.cpp:38:13: note: while referencing 'c'
   38 |  ar<int, 2> c {};
      |             ^
snake_escaping.cpp:52:11: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
   52 |   if(c[2] <= 6){
snake_escaping.cpp:38:13: note: while referencing 'c'
   38 |  ar<int, 2> c {};
      |             ^

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