Submission #1036960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036960		arashMLG	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	4444 KiB

snake_escaping

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...)    69
#define debugArr(...)  69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 5e5 + 23;
const int LOG = 20;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int n,q;
int a[1<<LOG];
int sub[1<<LOG],super[1<<LOG];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>q;
	for(int i = 0 ;i < (1 << n) ; i ++) {
		char c; cin>>c;
		a[i] = c-'0';
		super[i] = sub[i] = a[i];
	}
	for(int i = 0 ; i < n; i++) for(int mask =0 ;mask < (1  << n); mask++) {
		if((mask >> i)&1) sub[mask] += sub[mask^(1<<i)];
		else              super[mask] += super[mask^(1<<i)];
	}
	while(q--) {
		int mask0=0,mask1=0,maskq=0;
		string str; cin>>str;
		reverse(all(str));
		for(int i = 0 ; i < n; i ++) {
			char c= str[i];
			if(c == '0') {
				mask0 |= (1 << i);
			} else if(c == '1') {
				mask1 |= (1 << i);
			} else {
				maskq |= (1 << i);
			}
		}
		if(__builtin_popcount(maskq) <= n/3) {
			int ans =0;
			for(int s = maskq; ;s = s&(s-1)) {
				ans += a[s|mask1];
				if(s == 0) break;
			}		
			cout<<ans << '\n';
		} else if(__builtin_popcount(mask1) <= n/3) {
			int ans = 0;
			for(int s = mask1; ; s = s&(s-1)) {
				int zarib = ((__builtin_popcount(mask1)-__builtin_popcount(s))&1 ? -1 : 1);
				ans += zarib * sub[maskq | s];
				if(s == 0) break;
			}
			cout<<ans << '\n';
		} else {
			int ans =0;
			for(int s = mask0; ; s = s&(s-1)) {
				int zarib = (__builtin_popcount(s)&1 ? -1 : 1);
				ans += zarib * super[mask1|s];
				if(s == 0) break;
			}
			cout<<ans << '\n';
		}
	}
	return 0;
}

// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!

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