Submission #1278572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278572		nanaseyuzuki	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	210 ms	25396 KiB

snake_escaping

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 1e6 + 5, lg2 = 20, mbit = (1 << 20) + 1, mm = 5e3 + 5, mod = 1e6 + 3, inf = 1e18;

int l, q, a[mn], small[mn], big[mn];
string s;

void solve(){
	cin >> l >> q;
	cin >> s;
	for(int i = 0; i < (1 << l); i++) a[i] = small[i] = big[i] = s[i] - '0';

	for(int i = 0; i < l; i++){
		for(int mask = 0; mask < (1 << l); mask ++){
			if(mask & (1 << i)) small[mask] += small[mask ^ (1 << i)]; 
			else big[mask] += big[mask ^ (1 << i)];
		}	
	}

	while(q--){
		string s; cin >> s;
		reverse(all(s));
		int cnt0 = 0, mask0 = 0;
		int cnt1 = 0, mask1 = 0;
		int cnt_ = 0, mask_ = 0;
		for(int i = 0; i < l; i++){
			if(s[i] == '0') cnt0 ++, mask0 |= (1 << i);
			if(s[i] == '1') cnt1 ++, mask1 |= (1 << i);
			if(s[i] == '?') cnt_ ++, mask_ |= (1 << i);
		}
		if(cnt_ <= 6){
			int res = a[mask1];
			for(int sub = mask_; sub; sub = (sub - 1) & mask_){
				res += a[mask1 | sub];
				// cout << (mask1 | sub) << ' ' << a[mask1 | sub] << '\n';
			}
			cout << res << '\n';
		}
		// BHLT
		else if(cnt1 <= 6){
			int res = small[mask_] * (__builtin_popcount(mask1) % 2 ? - 1 : 1);
			for(int sub = mask1; sub; sub = (sub - 1) & mask1){
				int cnt = __builtin_popcount(sub ^ mask1);
				if(cnt % 2 == 1) res -= small[sub | mask_];
				else res += small[sub | mask_];
			}
			cout << res << '\n';
		}
		else if(cnt0 <= 6){
			int res = big[mask1];
			for(int sub = mask0; sub; sub = (sub - 1) & mask0){
				int cnt = __builtin_popcount(sub);
				if(cnt % 2 == 1) res -= big[sub | mask1];
				else res += big[sub | mask1];
			}
			cout << res << '\n';
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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