Submission #590285

#	Time	Username	Problem	Language	Result	Execution time	Memory
590285		blue	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1587 ms	46212 KiB

snake_escaping

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
#define sz(x) int(x.size())

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int L, Q;
	cin >> L >> Q;

	vi A((1<<L));
	for(int i = 0; i < (1<<L); i++)
	{
		char c;
		cin >> c;
		A[i] = c - '0';
	}

	vi lowersum = A;

	vi uppersum = A; 
	reverse(uppersum.begin(), uppersum.end());

	for(int b = 0; b < L; b++)
	{
		for(int i = 0; i < (1<<L); i++)
		{
			if(i & (1<<b))
			{
				lowersum[i] += lowersum[i ^ (1<<b)];
				uppersum[i] += uppersum[i ^ (1<<b)];
			}
		}
	}

	vi getbit((1<<L));
	for(int i = 0; i < L; i++)
		getbit[(1<<i)] = i;

	for(int j = 0; j < Q; j++)
	{
		vi p0, p1, pq;

		int onemask = 0;
		int qmask = 0;
		int zeromask = 0;

		for(int b = L-1; b >= 0; b--)
		{
			char c;
			cin >> c;

			if(c == '0')
			{
				p0.push_back(b);
				zeromask += (1<<b);
			}
			else if(c == '1')
			{
				p1.push_back(b);
				onemask += (1<<b);
			}
			else
			{
				pq.push_back(b);
				qmask += (1<<b);
			}
		}

		int res = 0;


		if(sz(p1) <= 6)
		{
			// cerr << "p1 size = " << sz(p1) << '\n';
			vi ssum((1 << sz(p1)), 0);
			vi sign((1 << sz(p1)), +1);

			if(sz(p1) % 2 == 0)
				sign[0] = +1;
			else
				sign[0] = -1;

			for(int m = 1; m < (1<<sz(p1)); m++)
			{
				ssum[m] = ssum[m - (m&-m)] + (1 << p1[getbit[m&-m]]);
				sign[m] = -1 * sign[m - (m&-m)];
			}

			for(int m = 0; m < (1<<sz(p1)); m++)
			{
				// cerr << "m = " << m << '\n';
				// cerr << "sign = " << sign[m] << '\n';
				res += lowersum[qmask | ssum[m]] * sign[m];
			}
		}
		else if(sz(p0) <= 6)
		{
			// cerr << "p0 size = " << sz(p0) << '\n';
			vi ssum((1 << sz(p0)), 0);
			vi sign((1 << sz(p0)), +1);

			if(sz(p0) % 2 == 0)
				sign[0] = +1;
			else
				sign[0] = -1;

			for(int m = 1; m < (1<<sz(p0)); m++)
			{
				ssum[m] = ssum[m - (m&-m)] + (1 << p0[getbit[m&-m]]);
				sign[m] = -1 * sign[m - (m&-m)];
			}

			// cerr << "qmask = " << qmask << '\n';

			for(int m = 0; m < (1<<sz(p0)); m++)
			{
				// cerr << m << " -> " << ssum[m] << '\n';
				res += uppersum[qmask | ssum[m]] * sign[m];
			}
		}
		else// if(sz(pq) <= 6)
		{
			vi ssum((1 << sz(pq)), 0);
			for(int m = 1; m < (1<<sz(pq)); m++)
				ssum[m] = ssum[m - (m&-m)] + (1 << pq[getbit[m&-m]]);

			for(int m = 0; m < (1<<sz(pq)); m++)
				res += A[onemask | ssum[m]];
		}

		// cerr << test << ' ' << mask << '\n';

		cout << res << '\n';
	}
}

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