Submission #939364

#	Time	Username	Problem	Language	Result	Execution time	Memory
939364		a_l_i_r_e_z_a	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	568 ms	34396 KiB

snake_escaping

// In the name of God
// Hope is last to die
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
 
const int maxn = 1ll << 20;
const int inf = 1e9 + 7;
int n, q, dp[maxn], pd[maxn], res[70];
string s; 
vector<int> pos;

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    cin >> s;
    for(int i = 0; i < (1ll << n); i++){
        dp[i] = pd[(1ll << n) - 1 - i] = s[i] - '0';
    }
    for(int i = 0; i < n; i++){
        for(int mask = 0; mask < (1ll << n); mask++){
            if(!(mask & (1ll << i))){
                dp[mask] += dp[mask + (1ll << i)];
                pd[mask] += pd[mask + (1ll << i)];
            }
        }
    }
    while(q--){
        string t; cin >> t;
        reverse(all(t));
        int one = count(all(t), '1');
        int zero = count(all(t), '0');
        int ques = count(all(t), '?');
        int ans = 0;
        pos.clear();
        if(ques < 7){
            int mask = 0;
            for(int i = 0; i < n; i++){
                if(t[i] == '1') mask += 1ll << i;
                if(t[i] == '?') pos.pb(i);
            }
            res[0] = mask;
            ans = s[mask] - '0';
            for(int i = 1; i < (1ll << ques); i++){
                int b = __builtin_ctz(i);
                res[i] = res[i - (1ll << b)] + (1ll << pos[b]);
                ans += s[res[i]] - '0';
            }
        }
        else if(zero < 7){
            int mask = 0;
            for(int i = 0; i < n; i++){
                if(t[i] == '1') mask += 1ll << i;
                if(t[i] == '0') pos.pb(i);
            }
            res[0] = mask;
            ans = dp[mask];
            for(int i = 1; i < (1ll << zero); i++){
                int b = __builtin_ctz(i);
                res[i] = res[i - (1ll << b)] + (1ll << pos[b]);
                if(__builtin_parity(i)) ans -= dp[res[i]];
                else ans += dp[res[i]];
            }
        }
        else{
            int mask = 0;
            for(int i = 0; i < n; i++){
                if(t[i] == '0') mask += 1ll << i;
                if(t[i] == '1') pos.pb(i);
            }
            res[0] = mask;
            ans = pd[mask];
            for(int i = 1; i < (1ll << one); i++){
                int b = __builtin_ctz(i);
                res[i] = res[i - (1ll << b)] + (1ll << pos[b]);
                if(__builtin_parity(i)) ans -= pd[res[i]];
                else ans += pd[res[i]];
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

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