Submission #1146698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146698		tnt	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	324 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#define pb push_back                    
#define ll long long
#define int long long
//#define sort(all(v)) sort(v.begin(),v.end())

int mod = 998244353;
const int N = 1e5 + 10;
const int inf = 1e9;



signed main(){
    //freopen("mootube.in", "r", stdin);
    //freopen("mootube.out", "w", stdout);
    int l,q;
    cin >> l >> q;                                
    string s;                                      
    cin >> s;
    vector <ll> dp(1 << l),dp1(1 << l);
    for(int i = 0; i < (1 << l); i++){
    	dp[i] = dp1[i] = s[i] - '0';
    }
    for(int i = 0; i < l; i++){
    	for(int mask = (1 << l) - 1; mask >= 0;mask--){
    		if(!(mask >> i & 1)){
    			dp1[mask] += dp1[mask + (1 << i)];
    		}
    	}
    }
    for(int i = 0; i < l; i++){
    	for(int mask = 0; mask < (1 << l) ;mask++){
    		if((mask >> i & 1)){
    			dp[mask] += dp[mask - (1 << i)];
    		}
    	}
    }                 
    while(q--){
        string t;                                 
        cin >> t;
        int cnt = 0,cnt1 = 0;
        for(int i = 0; i < l; i++){
        	if(t[i] == '?') cnt++;
        	else if(t[i] == '1') cnt1++;
        }
        if(cnt <= 6){
            int sum = 0,p = 0;
            ll ans = 0;
        	vector <int> v;
        	for(int i = t.size() - 1; i >= 0;i--){
        		if(t[i] == '1'){
        			sum += (1 << p);
        		}
        		else if(t[i] == '?'){
        			v.pb(p);
        		}
        		p++;
        	}
        	for(int mask = 0; mask < (1 << cnt); mask++){
        		int sum1 = 0;
        		for(int j = 0;j < cnt; j++){
        			if((mask >> j & 1) == 1){
        				sum1 += (1 << v[j]);
        			}
        		}
        		ans += s[sum + sum1] - '0';
        	}
        	cout << ans << '\n';
        }               
        else if(cnt1 > 6){
        	int p = 0,sum = 0;
        	ll ans = 0;
        	for(int i =  t.size() - 1; i >= 0; i--){
        		if(t[i] == '1') sum += (1 << p);
        		p++;
        	}
        	ans = dp1[sum];
        	vector <int> v;
        	p = 0;
        	for(int i =  t.size() - 1; i >= 0; i--){
        		if(t[i] == '0') v.pb(p);
        		p++;
        	}
        	for(int mask2 = 1; mask2 < (1 << v.size()); mask2++){
        		int sum1 = sum;
        		for(int j = 0; j < v.size(); j++){
        			if((mask2 >> j & 1) == 1)sum1 += (1 << v[j]);
        		}
        		if(__builtin_popcount(mask2) & 1){
        			ans += dp1[sum1];
        		}
        		else ans -= dp1[sum1];
       		}
       		cout << ans << '\n';
        }  
        else{
        	int p = 0,sum = 0;
        	ll ans = 0;
        	for(int i =  t.size() - 1; i >= 0; i--){
        		if(t[i] == '0') sum += (1 << p);
        		p++;
        	}
        	ans = dp[sum];
        	vector <int> v;
        	p = 0;
        	for(int i =  t.size() - 1; i >= 0; i--){
        		if(t[i] == '1') v.pb(p);
        		p++;
        	}
        	for(int mask2 = 1; mask2 < (1 << v.size()); mask2++){
        		int sum1 = sum;
        		for(int j = 0; j < v.size(); j++){
        			if((mask2 >> j & 1) == 1)sum1 += (1 << v[j]);
        		}
        		if(__builtin_popcount(mask2) & 1){
        			ans += dp[sum1];
        		}
        		else ans -= dp[sum1];
       		}
       		cout << ans << '\n';

        }

    }
    
}

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