Submission #535014

#	Time	Username	Problem	Language	Result	Execution time	Memory
535014		pooyashams	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2013 ms	17732 KiB

snake_escaping

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int lgmx = 20;
const int maxn = (1<<lgmx);

int val[maxn];
int sub[maxn];
int sup[maxn];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int L, q; cin >> L >> q;
	const int n = (1<<L);
	for(int i = 0; i < n; i++)
	{
		char c; cin >> c;
		val[i] = c-'0';
		sub[i] = val[i];
		sup[i] = val[i];
	}
	for(int j = 0; j < L; j++)
		for(int i = 0; i < n; i++)
			if((i>>j) & 1)
				sub[i] += sub[i^(1<<j)];
	for(int j = L-1; j >= 0; j--)
		for(int i = n-1; i >= 0; i--)
			if((i>>j) & 1)
				sup[i^(1<<j)] += sup[i];
	vector<int> vec[3];
	for(int i = 0; i < 3; i++) vec[i].reserve(20);
	const int l3 = L/3;
	while(q--)
	{
		for(int i = 0; i < 3; i++) vec[i].clear();
		string s; cin >> s;
		reverse(s.begin(), s.end());
		for(int i = 0; i < L; i++)
		{
			if(s[i] == '?')
				vec[2].push_back(i);
			else
				vec[s[i]-'0'].push_back(i);
		}
		if((int)(vec[0].size()) <= l3)
		{
			int a = vec[0].size();
			int k = 0;
			for(int j: vec[1]) k ^= (1<<j);
			int ans = 0;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = i; j > 0; j -= j&-j)
					x ^= (1<<vec[0][__builtin_ctz(j)]);
				if(__builtin_popcount(i) & 1)
					ans -= sup[x];
				else
					ans += sup[x];
			}
			cout << ans << endl;
		}
		else if((int)(vec[1].size()) <= l3)
		{
			int a = vec[1].size();
			int k = 0;
			for(int j: vec[2]) k ^= (1<<j);
			int ans = 0;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = i; j > 0; j -= j&-j)
					x ^= (1<<vec[1][__builtin_ctz(j)]);
				if( (a-__builtin_popcount(i)) & 1)
					ans -= sub[x];
				else
					ans += sub[x];
			}
			cout << ans << endl;
		}
		else
		{
			int a = vec[2].size();
			int k = 0;
			for(int j: vec[1]) k ^= (1<<j);
			int ans = 0;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = i; j > 0; j -= j&-j)
					x ^= (1<<vec[2][__builtin_ctz(j)]);
				ans += val[x];
			}
			cout << ans << endl;
		}
	}
	return 0;
}

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