Submission #539327

#	Time	Username	Problem	Language	Result	Execution time	Memory
539327		pnm1384	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1516 ms	39272 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 21;
int dp[1 << N], dp2[1 << N], cnt[3], bads[N];
string ss;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int len, q;
	cin >> len >> q >> ss;
	for (int i = 0; i < (1 << len); i++)
	{
		dp[i] = ss[i] - '0';
		dp2[i] = ss[i] - '0';
	}
	for (int i = 0; i < len; i++)
	{
		for (int mask = 0; mask < (1 << len); mask++)
		{
			if (!((mask >> i) & 1)) dp[mask] += dp[mask ^ (1 << i)];
			else dp2[mask] += dp2[mask ^ (1 << i)];
		}
	}
	for (int jj = 0; jj < q; jj++)
	{
		string s2;
		cin >> s2;
		reverse(s2.begin(), s2.end());
		for (int j = 0; j < 3; j++) cnt[j] = 0;
		for (int i = 0; i < len; i++)
		{
			if (s2[i] == '?') cnt[0]++;
			else cnt[s2[i] - '0' + 1]++;
		}
		int ans = 0;
		if (cnt[0] <= 6)
		{
			int msk = 0;
			for (int i = 0; i < len; i++)
			{
				if (s2[i] == '1') msk ^= (1 << i);
			}
			int ttt = 0;
			for (int i = 0; i < len; i++)
			{
				if (s2[i] == '?') bads[ttt++] = i;
			}
			for (int mask = 0; mask < (1 << ttt); mask++)
			{
				int msk2 = msk;
				for (int i = 0; i < ttt; i++)
				{
					if ((mask >> i) & 1) msk2 |= (1 << bads[i]);
				}
				ans += ss[msk2] - '0';
			}
			cout << ans << '\n';
			continue;
		}
		if (cnt[1] <= 6)
		{
			int msk = 0;
			for (int i = 0; i < len; i++)
			{
				if (s2[i] == '1') msk ^= (1 << i);
			}
			int ttt = 0;
			for (int i = 0; i < len; i++)
			{
				if (s2[i] == '0') bads[ttt++] = i;
			}
			for (int mask = 0; mask < (1 << ttt); mask++)
			{
				int msk2 = msk;
				for (int i = 0; i < ttt; i++)
				{
					if ((mask >> i) & 1) msk2 |= (1 << bads[i]);
				}
				int f = 1;
				if (__builtin_parity(mask)) f = -1;
				ans += f * dp[msk2];
			}
			cout << ans << '\n';
			continue;
		}
		int msk = 0;
		for (int i = 0; i < len; i++)
		{
			if (s2[i] == '?' || s2[i] == '1') msk ^= (1 << i);
		}
		int ttt = 0;
		for (int i = 0; i < len; i++)
		{
			if (s2[i] == '1') bads[ttt++] = i;
		}
		for (int mask = 0; mask < (1 << ttt); mask++)
		{
			int msk2 = msk;
			for (int i = 0; i < ttt; i++)
			{
				if ((mask >> i) & 1) msk2 ^= (1 << bads[i]);
			}
			int f = 1;
			if (__builtin_parity(mask)) f = -1;
			ans += f * dp2[msk2];
		}
		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