Submission #248516

#	Time	Username	Problem	Language	Result	Execution time	Memory
248516		Berted	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1314 ms	47632 KiB

snake_escaping

#include <iostream>
#include <utility>
#include <tuple>
using namespace std;

const int SZ = 1 << 20;

int n, q, k;
string s;
string qry;

int dp[2][2][SZ] = {};
int cr[8], sz = 0;

/*
	We can decompose a query into three types,
	min(0, 1, ?) == 0, min(0, 1, ?) == 1, min(0, 1, ?) == ?
	Then, we could find an algorithm that runs in 2^k for each possible type
	Since k is at most 6, 2^k is at most 64, therefore 2^k * Q still works.
*/

int qry1(int i, int val)
{
	if (i < sz) {return qry1(i + 1, val) + qry1(i + 1, val ^ cr[i]);}
	else {return s[val] - '0';}
}

int qry2(int t, int i, int val, bool c)
{
	if (i < sz) {return qry2(t, i + 1, val, c ^ t) + qry2(t, i + 1, val ^ cr[i], c ^ (!t));}
	else 
	{
		if (c) return -dp[t][n & 1][val];
		else return dp[t][n & 1][val];
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	cin >> s;
	k = s.size();
	for (int i = 0; i < k; i++) {dp[0][0][i] = dp[1][0][i] = s[i] - '0';}
	for (int i = 1; i <= n; i++)
	{
		int cri = i & 1, pv = !cri, msk = 1 << (i - 1);
		for (int j = 0; j < k; j++)
		{
			for (int k = 0; k < 2; k++)
			{
				dp[k][cri][j] = dp[k][pv][j];
				if (((j & msk) > 0) ^ !k) dp[k][cri][j] += dp[k][pv][j ^ msk];
			}
		}
	}
	for (int i = 0; i < q; i++)
	{
		cin >> qry;
		int a = 0, b = 0, c = 0, mn;
		for (int j = 0; j < n; j++)
		{
			a += (qry[j] == '0');
			b += (qry[j] == '1');
			c += (qry[j] == '?');
		}
		mn = min(a, min(b, c));
		if (mn == a) 
		{
			int val = 0;
			for (int j = 0; j < n; j++) 
			{
				if (qry[j] == '0') cr[sz++] = 1 << (n - 1 - j);
				else if (qry[j] == '1') val ^= 1 << (n - 1 - j);
			}
			cout << qry2(0, 0, val, 0) << "\n";
		}
		else if (mn == b) 
		{
			int val = 0;
			for (int j = 0; j < n; j++) 
			{
				if (qry[j] == '1') cr[sz++] = 1 << (n - 1 - j);
				else if (qry[j] == '?') val ^= 1 << (n - 1 - j);
			}
			cout << qry2(1, 0, val, 0) << "\n";
		}
		else 
		{
			int val = 0;
			for (int j = 0; j < n; j++) 
			{
				if (qry[j] == '?') cr[sz++] = 1 << (n - 1 - j);
				else if (qry[j] == '1') val ^= 1 << (n - 1 - j);
			}
			cout << qry1(0, val) << "\n";
		}
		sz = 0;
	}
	return 0;
}

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