Submission #248508

#	Time	Username	Problem	Language	Result	Execution time	Memory
248508		Berted	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2029 ms	44708 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] = {};

/*
	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 < n)
	{
		if (qry[i] == '?') return qry1(i + 1, val << 1) + qry1(i + 1, (val << 1) ^ 1);
		else return qry1(i + 1, (val << 1) ^ (qry[i] - '0'));
	}
	else {return s[val] - '0';}
}

int qry2(int t, int i, int val, bool c)
{
	if (i < n)
	{
		if (qry[i] == '?') return qry2(t, i + 1, (val << 1) ^ t, c);
		else if (qry[i] - '0' == t) return qry2(t, i + 1, (val << 1), c ^ t) + qry2(t, i + 1, (val << 1) ^ 1, c ^ (!t));
		else return qry2(t, i + 1, (val << 1) ^ (qry[i] - '0'), c);
	}
	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) {cout << qry2(0, 0, 0, 0) << "\n";}
		else if (mn == b) {cout << qry2(1, 0, 0, 0) << "\n";}
		else {cout << qry1(0, 0) << "\n";}
	}
	return 0;
}

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