Submission #1259165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259165		nlsosad	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	328 KiB

snake_escaping

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[(1<<20)];
int f[(1<<20)], g[(1<<20)];
signed main(){
	int l, q;
	cin >> l >> q;
	string s;
	cin >> s;
	for (int i = 0;i<s.size();++i){
		a[i] = s[i]-'0';
		f[i] = a[i];
		g[i] = a[i];
	}
	int maxn = (1<<l);
	for (int i = 0;i<l;++i){
		for (int j = 0;j<maxn;++j){
			if(j&(1<<i)){
				f[j] += f[j ^ (1<<i)];
			}else{
				g[j] += g[j | (1<<i)];
			}
		}
	}
	// cout << g[0];return 0;
	while(q--){
		string t;
		cin >> t;
		reverse(t.begin(), t.end());
		int A = 0, B = 0, C = 0;
		for (int i = 0;i<l;++i){
			if(t[i]=='0'){
				A |= (1<<i);
			}else if(t[i]=='1'){
				B |= (1<<i);
			}else C |= (1<<i);
		}
		int res = 0;
		if(__builtin_popcount(C)<=(l/3)){
			// cout << "NGU ";
			int s = C;
			while(s>0){
				res += a[B|s];
				s = (s-1)&C;
			}
			res += a[B];
		}else if(__builtin_popcount(A)<=(l/3)){
			// cout << "LON ";
			int s = A;
			while(s>0){
				// cout << s << ' ';
				if(__builtin_popcount(s)%2==0){
					res += g[B|s];
				}else res-=g[B|s];
				s = (s-1)&A;
			}
			res += g[B];
		}else{
			// cout << "CAC ";
			int s = B;
			while(s>0){
				if(__builtin_popcount(s)%2==0){
					res += f[C|s];
				}else res-= f[C|s];
				s = (s-1)&B;
			}
			res += f[C];
		}
		cout << res << '\n';
	}
}

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