Submission #1183311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183311		GGOSHAB	Snake Escaping (JOI18_snake_escaping)	C++20	12 / 100	2093 ms	131072 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 = 6, P = pow(3, B);

map<int, int> b[1 << (20 - B)];

void solve() {
    int l, q;
    cin >> l >> q;
    int n = (1 << l);
    string s;
    cin >> s;
    vector<int> a(n);

    auto convert = [&](const vector<int> &d, int mask) {
        int res = 0;
        for (int i = 0; i < B; ++i) {
            if (mask >> i & 1) {
                res = 3 * res + 2;
            } else {
                res = 3 * res + d[i];
            }
        }
        return res;
    };

    for (int i = 0; i < n; ++i) {
        a[i] = s[i] - '0';
        ll l = i >> B;
        vector<int> d;
        ll x = i % (1 << B);
        while (x > 0) {
            d.push_back(x & 1);
            x >>= 1;
        }
        while (d.size() < B) {
            d.push_back(0);
        }
        for (int mask = 0; mask < (1 << B); ++mask) {
            int r = convert(d, mask);
            b[l][r] += a[i];
        }
    }

    while (q--) {
        string s;
        cin >> s;
        reverse(all(s));
        while (s.size() < B) {
            s.push_back(B);
        }
        vector<int> d(B);
        int mask = 0, left = 0;
        for (int i = 0; i < B; ++i) {
            d[i] = (s[i] == '1' ? 1 : 0);
            if (s[i] == '?') {
                mask |= (1 << i);
            }
        }

        int r = convert(d, mask);
        mask = 0;
        for (int i = 0; i < l - B; ++i) {
            if (s[i + B] == '?') {
                mask |= (1 << i);
            }
            if (s[i + B] == '1') {
                left |= (1 << i);
            }
        }

        ll ans = 0;
        for (int s = 0; s <= mask; s = ((s | ~mask) + 1) & mask) {
            ans += b[left | s][r];
            if (s == mask) 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