Submission #763105

#	Time	Username	Problem	Language	Result	Execution time	Memory
763105		sentheta	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	390 ms	20200 KiB

snake_escaping

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
#else
	#include"bits/stdc++.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}













const int N = 1<<18;

int lg, n, q;
string s;

int sub[N], super[N];

void solve1(){
	string t;
	cin >> t;
	reverse(all(t));
	// dbg(t);

	int a=0, b=0, c=0;
	rep(i,0,lg){
		if(t[i]=='0') a |= 1<<i;
		if(t[i]=='1') b |= 1<<i;
		if(t[i]=='?') c |= 1<<i;
	}
	// dbg(a); dbg(b); dbg(c);

	int ans = 0;
	if(bitcnt(a) <= 6){
		for(int z=a; ; z=(z-1)&a){
			int amt = super[b|z];
			if(bitcnt(z)&1) amt *= -1;
			ans += amt;

			if(z==0) break;
		}
	}
	else
	if(bitcnt(b) <= 6){
		for(int z=b; ; z=(z-1)&b){
			int amt = sub[c|z];
			if(bitcnt(z^b)&1) amt *= -1;
			ans += amt;

			if(z==0) break;
		}
	}
	else
	if(bitcnt(c) <= 6){
		for(int z=c; ; z=(z-1)&c){
			ans += s[b|z]-'0';

			if(z==0) break;
		}
	}

	cout << ans << nl;
}

void solve(){
	
	cin >> lg >> q >> s;
	n = 1<<lg;
	
	rep(i,0,n){
		sub[i] = super[i] = s[i]-'0';
	}

	rep(b,0,lg) rep(msk,0,n){
		// include submask
		if(msk&1<<b){
			sub[msk] += sub[msk^1<<b];
		}
		// include supermask
		else{
			super[msk] += super[msk^1<<b];
		}
	}
	
	while(q--){
		solve1();
	}
	
	
	
	
}

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