Submission #535016

#	Time	Username	Problem	Language	Result	Execution time	Memory
535016		pooyashams	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1895 ms	42068 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()
{
	int L, q;
	scanf("%d %d", &L, &q);
	const int n = (1<<L);
	for(int i = 0; i < n; i++)
	{
		char c;
		scanf(" %c ", &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();
		for(int i = L-1; i >= 0; i--)
		{
			char c; scanf(" %c ", &c);
			if(c == '?')
				vec[2].push_back(i);
			else
				vec[c-'0'].push_back(i);
		}
		int ans = 0;
		if((int)(vec[0].size()) <= l3)
		{
			int a = vec[0].size();
			int k = 0;
			for(int j: vec[1]) k ^= (1<<j);
			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];
			}
		}
		else if((int)(vec[1].size()) <= l3)
		{
			int a = vec[1].size();
			int k = 0;
			for(int j: vec[2]) k ^= (1<<j);
			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];
			}
		}
		else
		{
			int a = vec[2].size();
			int k = 0;
			for(int j: vec[1]) k ^= (1<<j);
			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];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d %d", &L, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf(" %c ", &c);
      |   ~~~~~^~~~~~~~~~~~
snake_escaping.cpp:55:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |    char c; scanf(" %c ", &c);
      |            ~~~~~^~~~~~~~~~~~

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