Submission #1122187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122187		Mikael639	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	945 ms	56812 KiB

snake_escaping

#include <bits/stdc++.h>

#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define ForD(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

#define vi vector<int>

#define int long long

using namespace std;

const int N = (1 << 20) + 5;

int m, q, a[N], f[N], g[N];
string ss;
vi P[3];

void brute(){
	int M = 0;
	for (int i: P[1]) M |= (1 << i);
	int res = 0;
	rep(msk, 1 << sz(P[2])){
		int tmp = M;
		rep(i, sz(P[2])) if (msk & (1 << i)){
			tmp |= (1 << P[2][i]);
		}
		res += a[tmp];
	}
	cout << res << '\n';
}

void solve0(){
	
	int M = 0;
	for (int i: P[1]) M |= (1 << i);
	
	int res = 0;
	rep(msk, 1 << sz(P[0])){
		int tmp = M;
		rep(i, sz(P[0])) if (msk & (1 << i)){
			tmp |= (1 << P[0][i]);
		}
		
		int sgn = __builtin_popcount(msk) & 1 ? -1 : +1;
		res += sgn * g[tmp];
	}
	
	cout << res << '\n';
}

void solve1(){
	int M = 0;
	for (int i: P[2]) M |= (1 << i);
	
	int res = 0;
	bool x = sz(P[1]) & 1 ? 1 : 0;
	
	rep(msk, 1 << sz(P[1])){
		int tmp = M;
		rep(i, sz(P[1])) if (msk & (1 << i)){
			tmp |= (1 << P[1][i]);
		}
		
		int sgn = (__builtin_popcount(msk) & 1) ^ x ? -1 : +1;
		res += sgn * f[tmp];
	}
	
	cout << res << '\n';
}

signed main(){

	ios_base::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0);
	
	cin >> m >> q >> ss;
	rep(i, 1 << m)
		a[i] = f[i] = g[i] = ss[i] - '0';
	
	rep(i, m) rep(msk, 1 << m){
		if (msk & (1 << i)){
			f[msk] += f[msk ^ (1 << i)]; 
			g[msk ^ (1 << i)] += g[msk];
		}
	}
	
	while (q--){
		string s; cin >> s;
		reverse(all(s));
		
		rep(i, m){
			if (isdigit(s[i])){
				P[s[i] - '0'].pb(i);
			}
			else P[2].pb(i);
		}
		
		if (sz(P[2]) <= 6) 
			brute();
		else if (sz(P[0]) <= 6) 
			solve0();
		else 
			solve1();
		
		rep(i, 3) P[i].clear();
	}

	return 0;
}

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