Submission #1183329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183329		GGOSHAB	Snake Escaping (JOI18_snake_escaping)	C++20	12 / 100	945 ms	9960 KiB

snake_escaping

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef ONPC
    #pragma GCC target("avx")
    #pragma GCC target("popcnt")

    #define cerr if (false) cerr
#endif

using namespace std;

#define all(v) begin(v), end(v)
#define watch(x) cerr << #x << ": " << x << endl;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;

mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
    return uniform_int_distribution<ll>(l, r)(gen64);
}

template<class T>
bool umin(T &a, const T &b) {
    return (a > b ? a = b, true : false);
}

template<class T>
bool umax(T &a, const T &b) {
    return (a < b ? a = b, true : false);
}

const int mod = 998244353;

ll mult(ll a, ll b) {
    return (a * b) % mod;
}

template<class T>
void add(T &a, const T &b) {
    a = (a + b) % mod;
}

const int inf = int(1e9) + 10;
const ll INF = ll(1e18) + 10;

const int maxn = 1e5 + 10;
constexpr int B = 10;

vector<int> sos_dp(vector<int> dp) {
    int n = __lg(dp.size());
    for (int bit = 0; bit < n; ++bit) {
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (mask >> bit & 1) {
                dp[mask] += dp[mask ^ (1 << bit)];
            }
        }
    }
    return dp;
}

void solve() {
    int l, q;
    cin >> l >> q;
    int n = (1 << l);
    string s;
    cin >> s;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        a[i] = s[i] - '0';
    }

    auto dp = sos_dp(a);
    while (q--) {
        string s;
        cin >> s;
        reverse(all(s));
        vector<int> d(l);
        int mask = 0, norm = 0;
        for (int i = 0; i < l; ++i) {
            d[i] = (s[i] == '1' ? 1 : 0);
            if (s[i] == '?') {
                mask |= (1 << i);
            }
            norm |= (d[i] << i);
        }

        int ans = 0;
        if (__builtin_popcount(mask) <= B) {
            for (int s = mask; s >= 0; s = (s - 1) & mask) {
                ans += a[norm | s];
                if (s == 0) break;
            }
        } else {
            for (int s = norm, k = +1; s >= 0; s = (s - 1) & norm, k *= -1) {
                ans += k * dp[s | mask];
                if (s == 0) break;
            }
        }

        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

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