제출 #535010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535010		pooyashams	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2069 ms	39336 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];

inline void pvc(const vector<int>& mf)
{
	for(int x: mf)
		cerr << x << " ";
	cerr << endl;
}

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];
	//for(int i = 0; i < n; i++)
	//	cerr << (bitset<3>(i)) << ": " << sub[i] << " " << sup[i] << endl;
	vector<int> vec[3];
	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 = 0; j < a; j++)
					if((i>>j) & 1)
						x ^= (1<<vec[0][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 = n-1;
			for(int j: vec[0]) k ^= (1<<j);
			int ans = 0;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = 0; j < a; j++)
					if(! ((i>>j) & 1) )
						x ^= (1<<vec[1][j]);
				if( (a-__builtin_popcount(i)) & 1)
					ans -= sub[x];
				else
					ans += sub[x];
			}
			cout << ans << endl;
		}
		else
		{
			//cerr << "here" << endl;
			int a = vec[2].size();
			int k = 0;
			for(int j: vec[1]) k ^= (1<<j);
			int ans = 0;
			//cerr << (bitset<4>(k)) << endl;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = 0; j < a; j++)
					if((i>>j)&1)
						x ^= (1<<vec[2][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