Submission #1247766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247766		vlomaczk	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1042 ms	41620 KiB

snake_escaping

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int l, q;
	cin >> l >> q;
	int n = 1<<l;
	vector<int> A(n);
	string s; cin >> s;
	for(int i=0; i<n; ++i) A[i] = s[i]-(int)'0';
	vector<int> F(n);
	for(int i = 0; i<(1<<l); ++i) F[i] = A[i];
	for(int i = 0; i < l; ++i) for(int mask = 0; mask < (1<<l); ++mask){
		if(mask & (1<<i))
			F[mask] += F[mask^(1<<i)];
	}
	vector<int> F2(n);
	for(int i = 0; i<(1<<l); ++i) F2[i] = A[i];
	for(int i = 0; i < l; ++i) for(int mask = 0; mask < (1<<l); ++mask){
		if(!(mask & (1<<i)))
			F2[mask] += F2[mask^(1<<i)];
	}
	while(q--) {
		string s;
		cin >> s;
		reverse(s.begin(), s.end());
		vector<int> zapytania, jedynki, zera;
		for(int i=0; i<l; ++i) {
			if(s[i]=='?') zapytania.push_back(i);
			if(s[i]=='1') jedynki.push_back(i);
			if(s[i]=='0') zera.push_back(i);
  		}
		if(zapytania.size() <= jedynki.size() && zapytania.size() <= zera.size()) {
			int x = zapytania.size();
			int base = 0;
			for(auto u : jedynki) base += 1<<u;
			int ans = 0;
			for(int msk = 0; msk<(1<<x); ++msk) {
				int m_base = base;
				for(int i=0; i<x; ++i) {
					if(msk&(1<<i)) m_base += 1<<zapytania[i];
				}
				ans += A[m_base];
			}
			cout << ans << "\n";
		} else if(jedynki.size() <= zapytania.size() && jedynki.size() <= zera.size()) {
			int x = jedynki.size();
			int base = 0;
			for(auto u : jedynki) base += 1<<u;
			for(auto u : zapytania) base += 1<<u;
			int ans = 0;
			for(int msk=0; msk<(1<<x); ++msk) {
				int ile0 = 0;
				int m_base = base;
				for(int i=0; i<x; ++i) {
					if(!(msk&(1<<i))) {
						ile0++;
						m_base -= 1<<jedynki[i];
					}
				}
				if(ile0%2==0) ans += F[m_base];
				else ans -= F[m_base];
			}
			cout << ans << "\n";
		} else {
			int x = zera.size();
			int base = 0;
			for(auto u : jedynki) base += 1<<u;
			int ans = 0;
			for(int msk=0; msk<(1<<x); ++msk) {
				int ile0 = 0;
				int m_base = base;
				for(int i=0; i<x; ++i) {
					if(!(msk&(1<<i))) {
						ile0++;
						m_base += 1<<zera[i];
					}
				}
				if(ile0%2==0) ans += F2[m_base];
				else ans -= F2[m_base];
			}
			cout << ans << "\n";
		}
	}

	return 0;
}

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