Submission #379384

#	Time	Username	Problem	Language	Result	Execution time	Memory
379384		cheissmart	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1464 ms	42220 KiB

snake_escaping

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 20;

int a[1 << 20], sub[1 << N], sup[1 << N];

signed main()
{
	IO_OP;
	
	int l, q;
	cin >> l >> q;
	for(int i = 0; i < (1 << l); i++) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	memcpy(sub, a, sizeof(a[0]) * (1 << l));
	memcpy(sup, a, sizeof(a[0]) * (1 << l));
	for(int j = 0; j < l; j++) {
		for(int i = 0; i < (1 << l); i++)
			if(i >> j & 1)
				sub[i] += sub[i ^ (1 << j)];
	}
	for(int j = 0; j < l; j++) {
		for(int i = 0; i < (1 << l); i++)
			if(i >> j & 1)
				sup[i ^ (1 << j)] += sup[i];
	}
	while(q--) {
		string s;
		cin >> s;
		reverse(ALL(s));
		int one = 0, zero = 0, any = 0;
		for(int i = 0; i < l; i++)
			if(s[i] == '1') one++;
			else if(s[i] == '0') zero++;
			else any++;
		int m1 = 0, m2 = 0;
		for(int i = 0; i < l; i++) {
			if(s[i] == '?') m2 |= 1 << i;
			else m1 |= (s[i] - '0') << i;
		}
		int mn = min({one, zero, any});
		if(one == mn) {
			int ans = 0;
			for(int m = m1; ; m = (m - 1) & m1) {
				int sign = (__builtin_popcount(m ^ m1) % 2 ? -1 : 1);
				ans += sign * sub[m | m2];
				if(m == 0) break;
			}
			cout << ans << '\n';			
		} else if(zero == mn) {
			int ans = 0;
			int all = ((1 << l) - 1) ^ m2;
			m1 ^= all;
			for(int m = m1; ; m = (m - 1) & m1) {
				int mm = all ^ m;
				int sign = (__builtin_popcount(m ^ m1) % 2 ? -1 : 1);
				ans += sign * sup[mm];
				if(m == 0) break;
			}
			cout << ans << '\n';
		} else {
			int ans = 0;
			for(int m = m2; ; m = (m - 1) & m2) {
				ans += a[m1 | m];
				if(m == 0) break;
			}
			cout << ans << '\n';
		}
	}

}

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