Submission #1125163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125163		Paz15	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1071 ms	17656 KiB

snake_escaping

//fast
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define rep(n) for (int i = 0 ; i<n ; i++)
#define pb push_back

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;
	int m = (1<<n);
	int norm[m];
	rep(m) norm[i] = s[i]-'0';
	rep(n){
		for (int j = m-1 ; j>=0 ; j--){
			if (j&(1<<i)){
				norm[j]+=norm[j-(1<<i)];
			}
		}
	}
	int odw[m];
	rep(m) odw[i] = s[i]-'0';
	rep(n){
		for (int j = 0 ; j<m-1 ; j++){
			if (!(j&(1<<i))){
				odw[j]+=odw[j+(1<<i)];
			}
		}
	}
	while (q--){
		string wej;
		cin >> wej;
		int zero = 0;
		int jed = 0;
		int zap = 0;
		for (char i : wej){
			if (i=='0') zero++;
			if (i=='1') jed++;
			if (i=='?') zap++;
		}
		if (zero<jed && zero<zap){
			int base = 0;
			vector<int> v;
			rep(n){
				if (wej[n-i-1]=='1') base+=(1<<i);
				if (wej[n-i-1]=='0') v.pb((1<<i));
			}
			ll w = 0;
			rep(1<<v.size()){
				int sum = base;
				int ile = v.size();
				for (int j = 0 ; j<v.size() ; j++){
					if ((1<<j)&i){
						ile--;
						sum+=v[j];
					}
				}
				if ((ile%2)==(v.size()%2)) w+=odw[sum];
				else w-=odw[sum];
			}
			cout << w << '\n';
		}else if (jed<zap){
			int base = 0;
			vector<int> v;
			rep(n){
				if (wej[n-i-1]=='?') base+=(1<<i);
				if (wej[n-i-1]=='1') v.pb(1<<i);
			}
			ll w = 0;
			rep(1<<v.size()){
				int sum = base;
				int ile = 0;
				for (int j = 0 ; j<v.size() ; j++){
					if ((1<<j)&i){
						ile++;
						sum+=v[j];
					}
				}
				if ((ile%2)==(v.size()%2)) w+=norm[sum];
				else w-=norm[sum];
			}
			cout << w << '\n';
		}else{
			int base = 0;
			vector<int> v;
			rep(n){
				if (wej[n-i-1]=='1') base+=(1<<i);
				if (wej[n-i-1]=='?') v.pb((1<<i));
			}
			int w = 0;
			rep(1<<v.size()){
				int sum = base;
				for (int j = 0 ; j<v.size() ; j++){
					if ((1<<j)&i){
						sum+=v[j];
					}
				}
				w+=s[sum]-'0';
			}
			cout << w << '\n';
		}
	}
}

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