Submission #234936

#	Time	Username	Problem	Language	Result	Execution time	Memory
234936		amoo_safar	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	2076 ms	20184 KiB

snake_escaping

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;

int s1[(1 << Log) + 2];
int L, Q;
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> L >> Q;
	str s;
	cin >> s;
	for(int i = 0; i < (1 << L); i++) s1[i] = s[i] - '0';
	for(int l = 0; l < L; l++)
		for(int i = 0; i < (1 << L); i++)
			if(i >> l & 1) s1[i ^ (1 << l)] += s1[i];
	while(Q --){
		cin >> s;
		int mk0 = 0, mk1 = 0;
		for(int i = 0; i < L; i++){
			if(s[i] == '1') mk1 |= (1 << (L - 1 - i));
			if(s[i] == '0') mk0 |= (1 << (L - 1 - i));	
		}
		int res = s1[mk1];
		int sub = mk0;
		while(sub){
			res += (__builtin_popcount(sub) & 1 ? -1 : 1) * s1[sub + mk1];
			sub = mk0 & (sub - 1);
		}
		cout << res << '\n';
	}
	return 0;
}

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