제출 #877159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
877159		OAleksa	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1043 ms	41968 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int maxn = 21;
int a[1 << maxn], cnt[1 << maxn], n, q, cnt1[1 << maxn];
string s;
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
   int tt = 1;
  	//cin >> tt;
   while (tt--) {
   	cin >> n >> q >> s;
   	for (int i = 0;i < (1 << n);i++) 
   		cnt[i] = cnt1[i] = (s[i] - '0');
   	for (int i = 0;i < n;i++) {
   		for (int mask = 0;mask < (1 << n);mask++) {
   			if (mask & (1 << i))
   				cnt[mask] += cnt[mask ^ (1 << i)];
   		}
   		for (int mask = (1 << n) - 1;mask >= 0;mask--) {
   			if (!(mask & (1 << i)))
   				cnt1[mask] += cnt1[mask ^ (1 << i)];
   		}
   	}
   	
   	while (q--) {
   		string t;
   		cin >> t;
   		reverse(t.begin(), t.end());
   		vector<int> a, b, c;
   		int x = 0;
   		for (int i = 0;i < n;i++) {
   			x += (t[i] == '1' ? (1 << i) : 0);
   			if (t[i] == '1')
   				a.push_back(i);
   			else if (t[i] == '0')
   				b.push_back(i);
   			else
   				c.push_back(i);
   		}
   		int ans = 0;
   		if (c.size() <= 6) {
   			for (int mask = 0;mask < (1 << (int)c.size());mask++) {
   				int y = x;
   				for (int j = 0;j < (int)c.size();j++) {
   					if (mask & (1 << j))
   						y |= (1 << c[j]);
   				}
   				ans += (s[y] - '0');
   			}
   		}
   		else if (a.size() <= 6) {
   			int tx = x;
   			for (int i = 0;i < n;i++)
   				tx += (t[i] == '?' ? (1 << i) : 0);
   			for (int mask = 0;mask < (1 << (int)a.size());mask++) {
   				int y = tx;
   				for (int j = 0;j < (int)a.size();j++) {
   					if (mask & (1 << j))
   						y -= (1 << a[j]);
   				}
   				ans += cnt[y] * (__builtin_popcount(mask) % 2 == 0 ? 1 : -1);
   			}
   		}
   		else {
   			for (int mask = 0;mask < (1 << (int)a.size());mask++) {
   				int y = x;
   				for (int j = 0;j < (int)a.size();j++) {
   					if (mask & (1 << j))
   						y += (1 << b[j]);
   				}
   				ans += cnt1[y] * (__builtin_popcount(mask) % 2 == 0 ? 1 : -1);
   			}
   		}
   		cout << ans << "\n";
   	}
	}
	return 0;
}

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