Submission #894754

#	Time	Username	Problem	Language	Result	Execution time	Memory
894754		coloboxx	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	578 ms	39412 KiB

snake_escaping

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,sse2,sse3,ssse3,sse4,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define ull unsigned ll
#define point pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
#define print(l, r) cerr << "[" << (#l) << ", " << (#r) << "] = ", _print(l, r), cerr << '\n'
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0)
template<class iter>
void _print(iter _first, iter _last) {
    while (_first != _last) {
        std::cerr << *(_first) << ' ';
        ++_first;
    }
}

const int N = 1 << 20;
const int S = 2e7 + 64;
const int INF = 1e9 + 64;
const ll MAX = 2e18 + 64;
const int LOG = 22;
const int MOD = 998244353;
const int P = 79;
const int B = 256;

using namespace std;
using namespace __gnu_pbds;

int dp[N][2];

int pw(int x) {
    return ((x & 1) ? -1 : 1);
}

int32_t main() {
    fast_io;

    int L, n, q;
    cin >> L >> q, n = 1 << L;

    string s;
    cin >> s;

    for (int i = 0; i < n; ++i)
        dp[i][0] = dp[i][1] = s[i] - '0';

    for (int i = 0; i < L; ++i)
        for (int mask = 0; mask < n; ++mask)
            if (mask >> i & 1)
                dp[mask][0] += dp[mask ^ (1 << i)][0];
            else
                dp[mask][1] += dp[mask ^ (1 << i)][1];

    while (q--) {
        string t;
        cin >> t;
        reverse(all(t));

        int base = 0, add = 0;
        int res = 0;

        if (count(all(t), '?') <= 6) {
            for (int i = 0; i < L; ++i)
                if (t[i] == '1') 
                    base |= 1 << i;
                else if (t[i] == '?')
                    add |= 1 << i;

            for (int j = add; ; j = (j - 1) & add) {
                res += s[base | j] - '0';
                if (j == 0)
                    break;
            }
        }
        else if (count(all(t), '0') <= 6) {
            for (int i = 0; i < L; ++i)
                if (t[i] == '1')
                    base |= 1 << i;
                else if (t[i] == '0')
                    add |= 1 << i;

            int cnt = __builtin_popcount(base);

            for (int j = add; ; j = (j - 1) & add) {
                int cur = base | j;
                res += dp[cur][1] * pw(__builtin_popcount(cur) - cnt);
                if (j == 0)
                    break;
            }
        }
        else {
            for (int i = 0; i < L; ++i) {
                if (t[i] != '0')
                    base |= 1 << i;
                if (t[i] == '1')
                    add |= 1 << i;
            }

            int cnt = __builtin_popcount(base);
            
            for (int j = add; ; j = (j - 1) & add) {
                int cur = base & ~j & (n - 1);
                res += dp[cur][0] * pw(cnt - __builtin_popcount(cur));
                if (j == 0)
                    break;
            }
        }

        cout << res << '\n';
    }
}

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