Submission #1181051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181051		AdamGS	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1173 ms	21788 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1<<20;
int T[LIM], dp0[LIM], dp1[LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q, l;
	cin >> l >> q; n=1<<l;
	string s;
	cin >> s;
	rep(i, n) dp0[i]=dp1[i]=T[i]=s[i]-'0';
	rep(i, l) rep(j, n) if(j&(1<<i)) dp1[j]+=dp1[j^(1<<i)]; else dp0[j]+=dp0[j^(1<<i)];
	while(q--) {
		string p;
		cin >> p;
		reverse(all(p));
		vector<int>A, B, C;
		rep(i, l) if(p[i]=='0') A.pb(i); else if(p[i]=='1') B.pb(i); else C.pb(i);
		int mask=0;
		rep(i, B.size()) mask|=1<<B[i];
		if((int)C.size()<=6) {
			int ans=0;
			rep(i, 1<<C.size()) {
				int mask2=mask;
				rep(j, C.size()) if(i&(1<<j)) mask2|=1<<C[j];
				ans+=T[mask2];
			}
			cout << ans << '\n';
		} else if((int)A.size()<=6) {
			int ans=0;
			rep(i, 1<<A.size()) {
				int mask2=mask;
				rep(j, A.size()) if(i&(1<<j)) mask2|=1<<A[j];
				if(__builtin_popcount(i)%2==0) ans+=dp0[mask2]; else ans-=dp0[mask2];
			}
			cout << ans << '\n';
		} else {
			int ans=0;
			mask=0;
			rep(i, C.size()) mask|=1<<C[i];
			rep(i, 1<<B.size()) {
				int mask2=mask;
				rep(j, B.size()) if(!(i&(1<<j))) mask2|=1<<B[j];
				if(__builtin_popcount(i)%2==0) ans+=dp1[mask2]; else ans-=dp1[mask2];
			}
			cout << ans << '\n';
		}
	}
}

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